[문제풀이] 02-05. 소수(에라토스테네스 체)

인프런, 자바(Java) 알고리즘 문제풀이

Array(1, 2차원 배열) - 0205. 소수(에라토스테네스 체)

🗒️ 문제

🎈 나의 풀이

	private static int solution(int n) {
        int answer = 0;
        int[] numbers = new int[n + 1];

        for(int i=0; i<numbers.length; i++) {
            numbers[i] = i;
        }

        for(int i=2; i<numbers.length; i++) {
            if(numbers[i] != 0) {
                for(int j=i*2; j<numbers.length; j+=i) {
                    numbers[j] = 0;
                }
            }
        }

        for(int i : numbers) {
            if(i != 0) answer++;
        }

        return answer - 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solution(n));
    }

🖍️ 강의 풀이

    public int solution(int n){
		int cnt=0;
		int[] ch = new int[n+1];
		for(int i=2; i<=n; i++){
			if(ch[i]==0){
				cnt++;
				for(int j=i; j<=n; j=j+i) ch[j]=1;
			}
		}
		return cnt;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		System.out.println(T.solution(n));
	}

💬 짚어가기

소수(prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.
따라서 1이 아니면서 자신보다 작은 수로 나누어 떨어지면 그 수는 소수가 아니다.

가장 간단한 로직은 반복문을 돌며 나누어 떨어지는 수가 있는지 확인하는 것이다.
하지만 테스트 케이스의 최대 개수는 20만으로 해당 방식으로 접근할 시 시간 초과다.

에라토스테네스 체를 이용하여 문제를 해결할 수 있다. 에라토스테네스 체는 임의의
자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법이다.

1. n개의 정수를 나열한다.
2. 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.
3. 다음 수 n을 기준으로 이후 n의 배수가 되는 수를 제거한다.
4. 3번을 반복한다.

나의 풀이에서는 소수를 모두 찾은 후에, 소수의 개수를 체크하도록 구현했다.
강의에서는 소수 여부를 체크함과 동시에 개수를 누계하도록 구현하여 코드가 더욱 간결하다.