1. 소수의 판정
ㅇ 에라토스테네스의 체(Eratosthenes' Sieve)가 유명
- (2부터 시작하여, 모든 정수의 배수를 체로 거르는 방법)
ㅇ 에라토스테라스 체 구현 例)
- (자바스크립트)
function eratosthenes(n) {
1 var p = [];
2 for (var i=2; i<=n; i++) p[i] = true; // 2 ~ n까지의 모든 정수를 일단 소수로 간주
3 var max = Math.floor(Math.sqrt(n)); // 소수 x는 √n까지 구하면 됨
4 var x = 2; // 최초의 소수
5 while (x <= max) { // √n 즉, max까지 반복
6 for (var i = 2 * x; i <= n; i += x) p[i] = false; // x의 배수들을 합성수로 처리
7 while(!p[++x]) /* empty */ ; // 다음 소수 x를 찾음
8 }
9 return p;
}
. 2 이상 자연수 n을 입력 받고, 배열 p를 반환
.. 배열 p 원소 각각이 소수이면 true, 합성수이면 false로 설정됨
. 1) 빈 배열 p 생성 ('0','1'을 제외한 n-1개 원소 필요)
. 2) 검토 대상 숫자는 모두 일단 true로 간주(초기화)시킴
. 3) p ≤ √n 까지의 숫자 만 고려하면 됨
. 4) 현재 처리중인 정수로써, p를 '2'로 초기화함
. 5~8) 합성수를 표시하는 2중 반복문
ㅇ 소수 판정 구현 例)
- (개요)
. 2 부터 시작하여 제곱근 보다 작은 수 까지, 나누어 떨어지지 않으면 소수로 판정
- (C 언어)
int is_prime (int n) {
int i;
if (n < 2) return 0;
for (i = 2; i*i < n; i++) { // i < n or i < n/2 or i*i < n
if (n % i == 0) return 0;
}
return i;
}
- (자바 언어)
public static boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i*i < n; i++) // i < n or i < n/2 or i*i < n
if (n % i == 0) return false;
return true;
}