[기초 알고리즘] 수학: 소수

소수란?

• 1과 자기 자신으로만 나누어지는 수 입니다.

 

판정법

for (int i = 2; i < N; i++) {
    if (N % i == 0) return false;    	
}

return true;

• 2부터 N-1까지 반복합니다.
• 반복하는 숫자가 N으로 나머지 연산하여 0인지 확인합니다.

 

에라토스테네스의 체

• 특정 범위 내의 소수판정법입니다.
• 반복하면서 합성수를 소거하는 방식입니다.

 

boolean[] nums = new boolean[N+1];
Arrays.fill(nums, true);

for (int i = 2; i <= Math.sqrt(N); i++) {
    if (!nums[i]) continue;    
    
    for (int j = i*i; j <= N; j += i) nums[j] = false;
}

List<Integer> answer = new ArrayList<>();
for (int k = 2; k <= N; k++) {
    if (!nums[k]) continue;
    
    answer.add(k);
}

return answer;

 

• 2부터 N까지 반복합니다.
• 현재 방문한 수의 배수를 소수가 아닌 수로 처리합니다.

 

골드바흐의 추측

• 2보다 큰 모든 짝수는 2개의 소수 합으로 표현 할 수 있음

 

 

출처

• BaaaaaaaarkingDog - 수학