[프로그래머스] 소수 찾기-JAVA

말하는 감자·2022년 6월 27일

Java 코딩테스트 프로그래머스

Programmers Level 1

목록 보기

22/66

프로그래머스 Level 1

🔒 소수 찾기

📚 문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

✅ 제한 사항

n은 2이상 1000000이하의 자연수입니다.

📖 입출력 예

n	result
10	4
5	3

📃 입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

🔨 첫번째 작성 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=2; i<n; i++) {
            boolean yn = false;
            for(int j=2; j<i/2; i++) {
                if(i % j == 0) yn = true;
            }
            if(!yn) answer++;
        }
        
        return answer;
    }
}

아 감자는 이중 for문 안좋아하긴 하는데 생각나는 방법이 이거뿐이였다.

1은 소수가 아니므로 2부터 시작하고 소수가 아니면 true이게 해놓아서 소수 여부를 체크한 후 answer에 1을 더했다.

그래도 나름 코드는 잘 적지 않았나 싶었는데

...에?

처음부터 다시 생각해보자... 일단 초기화...
그리고 질문하기에 방문...!!

음... 너무 복잡한걸? 🤕
일단 생각나는 대로 작성해보자!!

🔨 두번째 작성 코드

import java.util.ArrayList;

class Solution {
    public int solution(int n) {
        ArrayList<Integer> answ = new ArrayList<Integer>();
        answ.add(2);
        
        for(int i=3; i<=n; i+=2) {
            boolean yn = false;
            for(int j : answ) {
                if(i % j == 0) yn = true;
            }
            if(!yn) answ.add(i);
        }
        
        int answer = answ.size();
        
        return answer;
    }
}

질문하기에서 얻은 조언 중 1번, 3번만 적용했을 때의 코드이다.
n은 무조건 2 이상이므로 소수를 담아두는 리스트 answ에 미리 담아두고 3부터 2씩 증가하여(짝수는 약수 2를 가지므로 홀수만 비교) 소수 리스트 answ와 비교한다.

하지만 테스트 10에서 탈락...
제곱근을 사용하는 수 밖에 없는 것인가ㅠㅠ

🔨 세번째 작성 코드

import java.util.ArrayList;

class Solution {
    public int solution(int n) {
        int answer = 1; // 소수 2
        ArrayList<Integer> answ = new ArrayList<Integer>();
        
        for(int i=3; i<=n; i+=2) {
            boolean yn = false;
            for(int j : answ) {
                if(i % j == 0) yn = true;
            }
            if(!yn) {
                if(i <= Math.sqrt(n)) answ.add(i);
                else answer++;
            }
        }
        
        answer += answ.size();
        
        return answer;
    }
}

이번엔 n의 제곱근보다 작은 소수일 경우 리스트 answ에 담고 n의 제곱근보다 크면 그냥 answer의 수를 증가했다.
이렇게 한다면 n의 제곱근보다 큰 소수들은 굳이 비교하지 않으므로 비교수가 줄어들 것이다. 그렇다면 효율성 테스트도 통과하지 않을까?! 😀

~~응 아니야~~

질문하기에서 본 조언은 다 충족한 거 같은데 왜 통과를 못하는 걸까...😵

다시 질문하기에 방문!!

에라토스테네스의 체...??

🔍 에라토스테네스의 체

제곱근보다 작은 소수들의 배수를 지우고 남는 수는 모두 소수이다!!

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다

그림의 경우, 11^2>120이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

📑 출처

위키피디아

오오!! 그러니깐 이거 다 갈아엎고 공부해야한다는 소리지?! 🥴
위키피디아 가면 아래에 친히 언어별 코드까지 다 있다

🗝️ 네번째 작성 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int[] number = new int[n+1];
        
        for(int i = 0; i < n+1; i++) number[i] = i;
        
        for(int i = 2; i < n+1; i++) {
            if(number[i] != 0) {
                for(int j=i+i; j<n+1; j+=i) {
                    number[j] = 0;
                }
            }
        }
        
        for(int i = 2; i < n+1; i++) {
            if(number[i] != 0) answer++;
        }
        
        return answer;
    }
}