소수 (Prime Number) 찾기 - 2

해당 게시글은 제곱근 범위를 이용해 소수 찾기를 구현한 내용입니다.

- 소수 (Prime Number) 찾기 - 1

- 소수 (Prime Number) 찾기 - 3

 

해당 숫자의 소수 여부를 판단할 때 해당 숫자의 루트값까지만 계산한다. 
이때 나누어 떨어지지 않으면 소수가 아니다!

 

Q) 왜 소수 검사할 때 N의 제곱근까지만 할까? 

A) N은 소수가 아닌 합성수로 A * B = N 이 가능하다. (A > B)

    N의 제곱근을 X라고 두면, N = A * B = X * X 성립한다.

    A > X 라고 하면, B ≤ X가 되어야 하므로 B ≤ X < A 가 되므로 

    소수를 찾을 때, 제곱근 X (≥ B)까지만 찾으면 확인할 수 있다.

 

소수 (Prime Number) 찾기 - 1방식과 비교하면

연산 범위를 [2, N]에서 [2, √N] 까지로 변경한 부분이다.

ex)  「13」  소수인지 판단하는 것은 제곱근이 3.xxx 이므로 3까지만 나누어 본다.

 

[Java]

public class Main {
     public static void main(String[] args) {
           long startTime = System.currentTimeMillis();
            
           int N = 100000;
           int arr[] = new int[N + 1];
            
           arr[1] = 1; // 1은 소수가 아니다.
           for(int i=2; i<=N; i++){
                for(int j=2; j*j<=i; j++) {
                      if(i%j == 0) {
                           arr[i] = 1;
                           break;
                      }
                }
           }
            
           int cnt = 0;
           for(int i=2; i<=N; i++){
                if(arr[i] == 0){
                      cnt++;
                }
           }
            
           long endTime = System.currentTimeMillis();
           System.out.println("2 ~ " + N +" 까지 소수 개수: " +  cnt);
           System.out.println( "경과시간: " + (endTime -  startTime));
     }
}

 

[2~100000까지 소수 개수 및 경과시간 확인]

 

[관련 문제]

- [BOJ] 1747 소수&팰린드롬

- [Jungol] 1901 소수 구하기