소수(Prime Number) 찾기 - 1

소수(Prime Number)란?

1과 자기자신으로만 나누어지는 숫자

ex) 2, 3, 5, 7, ... 

★ 소수를 구하는 방법은 크게 3가지 방식이 존재한다.

    ① 2 ~ N-1 까지 나누어지는지 확인

    ② 2 ~ √N 까지 나누어지는지 확인

    ③ 에라토스테네스의 체

각 방식을 통해서 효율적인 알고리즘에 대해 알 수 있습니다.

해당 게시글에서는 첫번째 방법에 대해서만 먼저 작성합니다.

- 소수 (Prime Number) 찾기 - 2

- 소수 (Prime Number) 찾기 - 3

 

소수 여부 확인할 때, 가장 먼저 떠오르는 구현 방법은

정의(Definition)를 이용하는 것이다.

즉, 특정 숫자  「X」 에 대해서 2 ~ X - 1 까지 나누어 떨어지는 경우가 있는지 확인하는 방법이다.

직관적인 방법이지만 여러 숫자에 대해 소수 여부를 판단하는 경우에는 성능이 좋지 못한편이다.

 

[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<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] 2581 소수

[BOJ] 백준 2581 소수