6. 소수 판별

개념

• 정의: 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어떨어지지 않는 자연수

 

구현 방법

• 모든 약수가 가운데 약수(제곱근)를 기준으로 곱셈 연산에 대해 대칭을 이룸
  • 따라서, 특정 자연수의 약수를 찾을 때, 가운데 약수까지만 확인하면 됨

 

코드

public class Main {
    public static boolean isPrimeNum(int x){
        //2부터 x의 제곱근까지만 모든 수를 확인
        for(int i=2; i<=Math.sqrt(x); i++){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args){
        System.out.println(isPrimeNum(7));
    }
}

 

 

다수의 소수 판별

에라토스테네스의 체 알고리즘

• 정의: 특정수의 범위에 존재하는 모든 소수를 찾는 방법
• 시간복잡도: O(Nlog<logN>)
  • 거의 선형에 가까울 정도로 빠름
  • but, 범위에 해당하는 정도의 메모리 공간이 필요 
• 동작 과정
  1. 2부터 N까지의 모든 자연수 나열
  2. 2부터 n의 제곱근 까지의 아래 과정 반복
     
     • 남은 수 중 i의 배수를 모두 제거(i는 제거x)

 

 

코드

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        //1. 2~n까지의 자연수 준비
        int n = sc.nextInt();
        boolean[] arr = new boolean[n+1];
        Arrays.fill(arr, true);

        //2. 2~n의 제곱근까지 아래 과정 반복
        for(int i=2; i<=Math.sqrt(n); i++){
            if(arr[i] == true){
                for(int j=2; i*j <=n; j++){ //남은 수 중 i의 배수 모두 제거
                    arr[i*j] = false;
                }
            }
        }

        //3. 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i=2; i<=n; i++){
            if(arr[i]){
                sb.append(i + " ");
            }
        }
        System.out.println(sb);
    }
}