1978번 - 소수 찾기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int max = Integer.MIN_VALUE;
		int[] numbers = new int[N];
		for(int i=0;i<N;i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
			if(max < numbers[i]) {
				max = numbers[i];
			}
		}
		boolean[] isNotPrime = new boolean[max+1];
		isNotPrime[1] = true;
		for(int i=2;i<=Math.sqrt(max);i++) {
			if(!isNotPrime[i]) {
				for(int j=2*i;j<=max;j+=i) {
					isNotPrime[j] = true;
				}
			}
		}
		int result = 0;
		for(int i=0;i<N;i++) {
			if(!isNotPrime[numbers[i]]) {
				result++;
			}
		}
		System.out.println(result);
		br.close();
	}
}

 

시간이 84ms로 1위 기록 68ms에 크게 차이나지 않는 걸로 봐서는 최적에 가까운 듯.

 

이렇게 일정 범위 내의 소수를 모두 찾을 때는 에라토스테네스의 체가 효율적이고 특정한 수가 소수인지의 여부만을 알아야 할 때는 다른 소수 판별법이 더 효율적이라고 합니다.

 

소수 찾기(에라토스테네스의 체)는 꽤 유명한 주제이므로 백준 맞힌 사람에서 상위권 코드를 참고하는 걸 추천합니다.

 

 

간단하게 로직을 설명하면 다음과 같습니다.

 

기본적인 아이디어는 필요한 범위까지 2부터 에라토스테네스의 체를 돌려 해당 범위의 모든 소수를 구한 후 주어진 수를 일일히 대조하면서 소수의 개수를 알아내는 것입니다.

 

1. 먼저 입력을 받으면서 주어진 수 중 가장 큰 수를 알아내고(max)

2. 특정한 수가 소수인지를 기록하는 배열을 최댓값 까지 다루도록 max+1의 크기로 생성합니다(isNotPrime)

3. 1과 자기 자신 외의 인수는 2부터 루트 자기 자신의 배수만 따지면 되기 때문에 2부터 root(max)까지 for문을 돌립니다.

(루트보다 큰 값은 더 작은 인수를 계산할 때 이미 카운팅되어서 따질 경우 불필요한 계산이 됩니다.)

4. 이미 소수가 아닌 것으로 판정난 수를 제외하고(if문) 나머지 모든 소수에 대해 max보다 같거나 작은 모든 배수를 소수가 아닌 걸로 처리합니다.

5. 위 과정을 거치면 isNotPrime이 false인 index에 해당하는 수는 모두 소수가 됩니다. 전체 수에 대해 소수 여부를 판정하고 개수를 카운팅해서 출력합니다.