형태 번호가 1N + K인데, N은 약 1000이고 K는 정말 작습니다 (500 미만). 나는이 수를 소수성으로 테스트하려고한다. 현재 저는베이스 2로 페르마 (Fermat)의 테스트를 사용하고 있으며, 작은 요인 (< 10000)을 검사하기 전에 있습니다.형태의 숫자에 대한 소수성 테스트
그러나 이것은 내 목적에 비해 다소 느립니다. 그보다 빠른 알고리즘이 있습니까? 이 특별한 형태가 어떻게 든 악용 될 수 있습니까?
또한 두 개의 숫자가 K에서만 다른 경우이 두 숫자를 조금 더 빠르게 테스트 할 수 있습니까?
K가 2 또는 5 중 하나의 인자를 갖는다면, 10^N + K는 합성이다. 따라서 적은 수의 테스트를 신속하게 수행 할 수 있습니다. 큰 소수는 모두 P mod 6 = 1 또는 5입니다.이 값을 사용하여 가능한 K 값의 2/3을 제거 할 수 있습니다. 좋은 경우 10,000
increment <- either 2 or 4 as required
repeat
K <- K + increment
increment <- 6 - increment
if (K mod 5 = 0) then
continue
endif
until (isPrime(10^N + K) or (K > 500))
시험 고려해 최대 : 약간의 작업으로 당신은 분열의 많은 피하기 위해 2-4 바퀴를 설정할 수 있습니다. 당신은 10,000까지의 소수의리스트를 먼저 만들었습니까? Eratosthenes 'Sieve를 사용하여 목록을 만들고 숫자를 읽습니다.
페르마 테스트베이스 2를 실행하는 것이 좋은 출발이며, 합리적으로 많은 합성물을 발견합니다.
그런 다음 확률 Miller-Rabin 테스트를 구현하고 하드웨어가 실패했을 가능성이 높을 정도로 충분히 실행해야합니다.
또한 두 개의 숫자가 K에서만 다른 경우이 두 숫자를 조금 더 빠르게 테스트 할 수 있습니까?같은 비교적 작은 간격의 소수를 확인하기 [10 N + K 1 10 N + K 2] 가 작은 의해 정제를 확인 Erathostenes의 체를 사용하여 번호.
나머지 주요 후보는 Miller-Rabin과 같은 확률 테스트를 통해 확인할 수 있습니다.
나는 이것이 math.stackexchange.com에서 더 잘 다뤄 졌다고 생각한다. –
@raymond 나는 math.stackexchange.com에 글을 올릴 생각을 해왔다. 그러나 이것은 알고리즘과 수학에 관한 질문이기 때문에 거기에서 나의 운을 시험하기로 결정했다. – Artyom