[ 백준 1978 ] 소수 찾기

1. 문제 링크 https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

2. 문제

3. 문제 요약

주어진 1000이하의 자연수들 중 소수를 찾는 문제이다.

 

 

4. 문제 풀이

소수는 1과 자기 자신을 제외한 수로 나누어지지 않는 수이다.

(1) O ( N )

주어진 숫자 X에 대하여 1< i < N 범위의 i로 나누어지면 소수가 아니다.

*1은 소수가 아니지만, 식을 만족하지 못하므로 명시적으로 예외처리

 

(2) O( root(N) )

여기서 성능을 개선할 요소가 조금 더 있긴한데, 사실 N 까지 모두 확인할 필요가 없다.

N = a*b 이고 n 은 N의 제곱근이라 하면, 

a*b = N = n*n 이므로 a >= n 이면, b<=n 이다.

따라서 1 < i < n = root(N) 까지만 검사를 하면 된다.

 

(3) 연산속도 개선

Math.sqrt() 함수를 이용해서 root의 값을 이용해서 계산할 수는 있지만,

부동소숫점방식(float)을 이용한 계산은 성능적인 면에서 좋다고 볼 수 없다.

따라서 제곱근을 계산해서 비교하는 대신에, 연산숫자의 제곱을 이용해서 비교하면

 1 < i*i < N 의 범위를 검사하면 된다.

 

연산 횟수에서는 큰 차이가 없지만,

Math 를 이용하지 않아도 되고, 정수(integer)만으로 연산이 가능하기 때문에

성능면에서 개선이된다.

5. 풀이 코드

public static int problem1978() throws Exception {
    int n = Integer.parseInt(bfr.readLine());
    int ans = n;
    str = new StringTokenizer(bfr.readLine());
 
    for (int i = 0; i < n; i++) {
        int num = Integer.parseInt(str.nextToken());
        if (num == 1) {
            ans--;
            continue;
        }
 
        for (int j = 2; j * j <= num; j++) {
            if (num % j == 0) {
                ans--;
                break;
            }
        }
    }
    return ans;
}

public static int problem1978() throws Exception {
   int MAX = 1000 ;
 int n = Integer.parseInt(bfr.readLine());
    str = new StringTokenizer(bfr.readLine());
 
    int[] prime = new int[1+MAX];
    prime[1] = -1;
    for (int i = 2; i * i <= MAX; i++)
        for (int j = 2; j * i <= MAX; j++)
            prime[j * i] = -1;
 
    int ans = n;
    for (int i = 0; i < n; i++)
        ans += prime[Integer.parseInt(str1.nextToken())];
 
    return ans;
}