엄청 큰 소수 구하는 방법

in #jjangjjangman6 years ago (edited)

특정 2부터 시작하는 소수 리스트를 전부곱하고 거기에 1을 더하는 방법으로 엄청난 크기의 소수를 만들수 있다고 생각합니다.
이 수는 구지 소수인지 아닌지 판별할 필요가 없이 소수가 됩니다.

그 원리는
간단히 생각해서 숫자 1은 생각할필요없이 소수가 되지 않습니까??
그렇기때문에 2부터 시작한 소수리스트의곱 +1역시 소수가 되는 겁니다.
가령
2+1
2 * 3+1
2 * 3 * 5+1
2 * 3 * 5 * 7+1
2 * 3 * 5 * 7 * 11+1
...........
전부 소수입니다.
2를 제외하면 짝수가 됨으로 성립이 안됩니다.
(그러나 이렇게 생긴짝수는 특이한 성질을갖게됩니다. 3+1,3 * 5+1,(3 * 5+1+1) * 3 * 5+1,((3 * 5+1+1) * 3 * 5+1+1) * (3 * 5+1+1) * 3 * 5+1...................................................)

이를 발견해는것은 소수 수열을 구하는 방법을 생각하면서 얻어졌고요
아래는 제가 소수수열구하는 방법을 생각한것을 적어본 것입니다.
아래 제가 적은 생각에 의하여 2부터 차례로곱한 소수리스트에다 1을 더한값은 소수가됩니다.
아래 제가 그내용을 생각한 글 제목과 링크입니다.

제목:소수(素數) 수열 구하는 프로그램 알고리즘 구상해보기
링크:https://steemit.com/kr/@donworry8/6nityz

#jjangjjangman

여담으로
2+3
2 * 3+5
2 * 3 * 5+7
2 * 3 * 5 * 7+11
2 * 3 * 5 * 7 * 11+13
..........
역시 판별할 필요가 없이 소수가 됩니다.
또 한번 확장해서
2+7 ....성립안됨
2 * 3+7
2 * 3 * 5+11
2 * 3 * 5 * 7+13
2 * 3 * 5 * 7 * 11+17
..........
역시 소수가 됩니다.

그렇다면 모든 소수를 구하는데 도전해보겠습니다.

2+1
2 * 3+1,5
2 * 3 * 5+1,7,11,13,17,19....(위에 수열로 만들어진 수들,5x5제외)
2 * 3 * 5 * 7+1,11,13,17,19,23,27... 209(위에수열로 만들어진 수들,7,11,13등의 배수제외)
2 * 3 * 5 * 7*11+1,11,13,17,19,23,27........ (위에수열로 만들어진 수들,11,13,17등의 배수 제외)
...........
즉 소수은 이런 규칙으로 이루어진 가진 점화식 수열이 됩니다....
단계별로 특정범위의 모든 소수를 구할수있습니다.

Coin Marketplace

STEEM 0.28
TRX 0.11
JST 0.031
BTC 69266.11
ETH 3871.54
USDT 1.00
SBD 3.72