1. Trial Division 소수의 성질을 이용, 어떤 수 n 이 소수인지 판별하기 위해 n 을 2 부터 n-1 까지 하나씩 나누어보아 나누어 떨어지는 수가 존재하지 않으면 n 은 소수가 된다.
Notes - 2를 제외한 모든 소수는 홀수이므로, 어떤 수 n 이 짝수이면 소수가 아니다. - 만약 N 이 합성수라면 N = a*b 형태가 되므로 ( a > 1 && b > 1 ), a 와 b 둘 중 하나는 sqrt(N) 보다 작거나 같음을 알 수 있다. 그러므로 N 을 2부터 sqrt(N) 까지 나눠보아 나누어지지 않으면 N 은 소수가 된다.
void trial(int end) { for( int a = 2; a <= end; a++ ) { if( a%2 == 0 && a != 2 ) { prime[a] = 0; continue; }
2. 에라토스테네스의 체(Sieve of Eratosthenes) n 이 작을 때 ( 일반적으로 n <= 10,000,000 ) 2 부터 n 까지의 소수를 찾는 가장 효율적인 방법으로 알려져 있다. 어떤 수 P 가 소수이면 P 로 나눌 수 있는 P 의 배수들은 소수가 아닌 것으로 체크한다. 이러한 과정을 반복하면서 주어진 [2,n] 구간 내에서 소수를 찾아낸다.
void sieve(int end) { for( int a = 2; a*a <= end; a++ ) { if( prime[a] == 0 ) // 'a' is a prime { for( int b = a*2; b <= end; b += a ) prime[b] = 1; } } }
소수일 것 같은 수 (Probable Prime) 판별법 어떤 자연수 n 이 소수인지 아닌지 판별할 때, n 이 매우 커지면 유한시간내에 n 이 소수인지 판별하기 곤란해지게 된다. 이 때문에 n 의 소수 여부를 판별하는 근사해를 구하는 검사법이 여럿 개발되었는데, 이 검사법에 의해 n 이 합성수가 아님이 판별되는 경우에 n 을 소수일 것 같다 (Probable Prime) 고 한다. Probable Prime (PRP) 의 정의는, 소수가 갖는 특정 상태를 만족하는 자연수이다.
1. Wheel Factorization 소수의 특징 중 하나인 [2,n] 구간내에 존재하는 소수의 갯수는 n 이 커질 수록 분포도가 희박해진다는 점에서 착안한 방법. 에라토스테네스의 체의 특수한 응용방법이다. 기본 원리는 에라토스테네스의 체와 동일하나, 구간내의 모든 소수에 대해 배수를 찾아 검사하는 것이 아니라 몇개의 소수를 가지고 이 수들로 나누어지는 수들을 걸러내는 방식으로 구하는 것이 차이점이다. 소수 2, 3을 가지고 Wheel Factorization 을 한다면, 우선 2와 3 의 배수를 모두 소수가 아닌 것으로 판별한다. 그리고 그 다음 소수인 5, 7 를 이용해 또다시 이 작업을 반복한다. 일반적으로 많이 쓰는 factorization 은 6N+1, 6N+5 를 사용하여 주어진 구간 [1,n] 내에서 나누어 지지 않는 수를 소수일 것 같은 수로 판별한다. ( Wheel Factorization 은 n 이 커질수록 정확도가 떨어지므로 이를 위해 n 이 커질수록 더 많은 소수를 이용해 나누어보아야 한다. )
2. 페르마의 작은 정리 (Fermat's Little Theorem) 페르마의 마지막 정리로 유명한 수학자 페르마가 제안한 정리. p 가 a로 나눠지지 않는 소수라면 ap-1 = 1 (mod p) 를 만족해야 한다. 이때 상기 정리를 만족하지 않는 수는 합성수이며, 상기 정리를 만족하는 수는 소수일 가능성이 매우 높은 수(Probable Prime) 가 된다. 증명은 상기 링크 참조.
참고1 임의의 큰 자연수를 소인수분해하는 문제는 NP 문제로 알려져 있다. 거대한 합성수의 소인수분해는 암호문 해독에 응용되어, 기존의 암호문 전달 체계와 다른 암호학에 공공열쇠 개념을 도입하여 리베스트(Ron Rivest)와, 샤미르(Adi shamir), 아들만(Len Adleman)의 이름을 딴 RSA방식이라는 암호이론이 개발되기도 했다. http://mathworld.wolfram.com/PrimalityTest.html
페르마의 마지막 정리 라는 책을 읽다가 흥미로운 이야기가 있었다. 바로 "매미의 수명과 소수와의 관계" 라는 글이다. 매미의 수명은 종류마다 다르지만 그 분포를 보면 5년, 7년, 11년, 13년, 17년 등이 있다. 즉, 모두 소수(Prime Number) 를 이루고 있다. 왜 매미의 수명은 소수로 나타날까?
정리하자면 매미는 성충이 되었을 때 자신의 천적을 최대한 만나지 않기 위해서 애벌레로 지내는 시간 ( 자신의 수명 )을 연장하는 방향으로 진화해 왔는데, 무한정 수명을 연장할 수는 없는 노릇이므로 성충이 되는 시점에서 천적을 확률적으로 적게 만나는 소수 숫자의 수명을 갖게 되었다는 그럴듯한 이야기다. 천적의 수명주기와 매미의 수명주기가 서로소가 될 경우에 천적과 매미가 만나는 시점은 최대가 될 수 있기 떄문이다.
( 예를 들어 천적의 주기가 4년일 경우 매미의 수명이 8년이면 8년에 한 번씩은 반드시 매미는 천적과 만나게 된다. 그러나 매미의 수명이 7년이면 28년에 한번씩 천적과 만나게 된다. )
실제로 현존하는 모든 매미의 수명은 5년, 7년, 11년, 13년, 17년 과 같이 모두 소수로 이루어져 있다.
생활속의 수학이라고나 할까... ;) 꽤나 재미있다.
인터넷에 여기 저기 널리 퍼져있는 것을 보아 꽤나 유명한 이야기인 것 같다. 책에 원래 있던 내용에서 부연설명은 제외하고 출처도 밝히지 않고 대충 퍼온 글들도 꽤나 많이 보인다. -_-
for all 
앗.. 문득 제목에 오타가 보이네요.. finding primes 이네요..
땡큐!
급히 수정.. ^^
감사합니다. 좋은 정보 얻고 갑니다.
It's my pleasure~
좋은 포스트네요.
네 방문해 주셔서 감사합니다. ^^