N이 자연수중 소수(솟수?) 인지 아닌지 판별 해 내는 것을 생각해 보겠습니다.
첫째. 가장 쉽게 생각할 수 있는 알고리즘은
2~(N-1)까지의 수를 모두 하나씩 나머지 연산하여 그중 나머지가 0인 값인 수가 없으면 그 수는 소수입니다.
두번째.
저 위에서 N-1이 아니라 Sqrt(N) n의 제곱근 까지만 계산하는 것입니다.
세번째.
소수수열을 배열에 저장해놓고 그 배열안의 소수만 나머지연산을 하여 나머지가0이되는 수가 없으면 그수는 소수입니다.
세번째을 응용해서 소수 수열을 빨리 푸는방법을 생각해봅니다.
소수배열 [2,3,5]
가 있습니다. 이 세수로써 5~5x5까지의 소수를 찾아내서 그 배열안에 넣어줍니다.
[2,3,5,7,11,13,19,23]
2,3,5 세수로 7,11,13,19,23 5가지소수를 판별하여 배열에 첨가했습니다.
저 위배열로 23~23x23까지의 소수를 찾아내여 넣을수 있고
이를 무안히 반복해줍니다.
네번째
네번째 세번째방법을 응요한겁니다.
배열안의 숫자를 이용해 소수판별하는데 쓰는게 아니라
그 다음 소수가 아닌 수를 생성해내는데 쓰는겁니다. 생성할수 없으면 그수가 바로 솟수입니다.
[2,3,5]
위 수로 5~5x5 까지의 생성할수있는수를 생각해보겠습니다.
제곱수
2 4 8 16
3 9
5 25
06 = 2 x 3
07
08 = 2 x 4
09 = 3 x 3
10 = 2 x 5
11
12 = 2 x 6
13
14 = 2 x 7
15 = 3 x 5
보니까 짝수는 할 필요가 없으니 생략하고 홀수만 생각하겠습니다.
07
09 = 3 x 3
11
13
15 = 3 x 5
17
19
21 = 3 x 7
23
25 = 5 x 5
홀수는 홀수x홀수 에서만 생성된다는 점을 응용하면 됩니다. 2는 버려버리고
[3,5,7,11,13,17,19,23]의 조합으로 생성될수있는 23~23x23 모든 수를 생각하면되고 그수를 제외한 수가 소수수열이됩니다.
이수열을 판별이 아닌 생성을 목적으로 함으로 소수^n이 되는 제곱수도 포함시켜야 더 빨리 쉽게 연산될것같습니다.
[3,5,7,11,13,17,19,23] 여기에 5~5x5사의 소수의 제곱수가 되는 9와 25을 첨가함
[3,5,7,9,11,13,17,19,23,25]
다음수는
27 = 3 * 9
29
31
33 = 3 * 11
35 = 7 * 5
37
39= 3 * 13
이쯤 되면 2의 배수(짝수)제외 시켰던것처럼 3의 배수도 걍 제외시켜버리고 싶네요
[5,7,11,13,17,19,23,25]
35 = 5 * 7
37
41
43
49 = 7 * 7
51
53
55 = 5* 11
이로써 알고리즘을 다시 정리해보겠습니다.
규칙은 처음소수열
[2,3,5]에서 2의 배수는 생략하고 계산한다.
그러면 35와 33, 37, 55밖에 안남아
[3,5,7,11,13,17,19,23] 이 구해집니마
여기에 제곱수를 추가하고 제일 앞수인 3의 배수생략법을 사용합니다.
그러면 배열 [5,7,11,13,17,19,23,25]가 구해지며
이 배열로 조합되는 수들을 구하면 되고 그수들을 제외한것이 소수가 됩니다.
2,3,5의 배수가 아닌 수열은?
2의 배수가 아닌 수열은
2xN+1이 될것입니다.
3의 배수가 아닌 수열은
3xN+1 3xN+2가 될것입니다.
2의 배수도 3의 배수도 아닌 슈열은
6xN + 1, 6xN + 5 가 될것입니다.
2,3,5의 배수도 아닌 수열은
30xN + 1, 30xN + 7, 30xN + 11, 30xN + 13, 30xN + 17, 30xN + 19, 30xN + 23, 30xN + 29
가 됩니다.
여기까지왔으면 거의 다 된것 같습니다.
6xN + 1, 6xN + 5 로 생성되는 수열은
[1,5,13,17,19,23,25,29,31,35,37.......] 이 될것입니다......
이중에서 소수가 아닌수는
25,35 (5 x 5,5 x 7)입니다.
바로 [5,7,9,11...]수열에서 만들어지는 수순입니다.
25,35,45,49,55,63.............................이수숫자들을 제외하면 그게 솟수입니다.
그러면 [5,7,9] 세가지 수로 한정한다면 어디까지범위까지 솟수를 발견할수있을까요?
분명한것은 위수의 조합곱으로 만들어지는 수들중 가장작은수와 그다음 작은수 5 x 5와 5 x 7까지의 솟수는 확정적으로 구할수 있습니다.
즉 다시말해서
6xN + 1, 6xN + 5 이 수열로 7 x 5까지의 솟수 배열을 확실히 구할수 있고
그 수열배열로부터
2,3,5의 배수도 아닌 수열
30xN + 1, 30xN + 7, 30xN + 11, 30xN + 13, 30xN + 17, 30xN + 19, 30xN + 23, 30xN + 29
을 구할수있고
이 수열로 29x29,29x31까지의 솟수배열을 확실히 구할수 구할수 있습니다.
2,3,5의 배수도 아닌 수열
30xN + 1, 30xN + 7, 30xN + 11, 30xN + 13, 30xN + 17, 30xN + 19, 30xN + 23, 30xN + 29
에서 30~ 29x29까지 수들중 솟수가 아닌수들은
7 x 7
7 x 11
7 x 13
7 x 17
7 x 19
7 x 23
7 x 29
7 x 31
7 x 37
7 x 41.........에서 7 x 121까지....
그리고 11 x 11에서 11 x 121까지
13 x 13에서 13 x 121까지
17 x 17에서 17 x 121까지.......
등등의 수들을 제외하면그게 솟수가 됩니다.
이를계속 반복합니다.
2,3,5의 배수도 아닌 수열 에서다가 7 ,11 ,13 , 17, 19, 23, 29를 차례로 곱해준수를 제외해주면 됩니다.
(30xN + 1, 30xN + 7, 30xN + 11, 30xN + 13, 30xN + 17, 30xN + 19, 30xN + 23, 30xN + 29 ) * 7
= (210xN + 7, 210xN + 7x7, 210xN + 7x11, 210xN + 7x13, 210xN + 7x17, 210xN + 7x19, 210xN + 7x23, 210xN + 7x29 )
가 됩니다.
이러다가 '골드바흐추측'같은 것도 풀어내는지 모르겠는네여 ㅎㅎㅎ
다음 편에 직접 코드를 자바스키립트로 작성하는것 해보겠습니다.
스팀글에 코드를 넣을땐 '`'이거 x3연속으로 쓰면 된다고 하던데 처음으로 한번 쓰고싶어지네요
코드 abc
코드 abc
코드 abc
코드 abc
코드 abc
코드 abc
코드 abc
코드 abc
document.write("hello");