소수성을 어떻게 테스트할 수 있나요?
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 소수 관련 방법을 사용하여 작은 라이브러리를 작성 중입니다.기초 작업(일명 작업 방법)을 마쳤으므로 이제 몇 가지 최적화 방법을 찾고 있습니다.물론 인터넷은 그렇게 하기 위한 훌륭한 장소입니다.그런데 우연히 반올림 문제를 발견했고 이를 해결하는 방법이 궁금했습니다.
숫자의 소수성을 테스트하는 데 사용하는 루프에서는 n/2 또는 n - 1 대신 sqrt(n)까지 검색하는 것이 더 효율적입니다.그러나 반올림 문제로 인해 일부 숫자가 생략되고 일부 소수가 생략됩니다!예를 들어, 10000번째 소수는 다음과 같아야 합니다.104729이지만 '최적화된' 버전은 다음과 같이 끝납니다.103811.
일부 코드(더 많은 최적화를 위해 열려 있지만 한 번에 한 가지만 처리할 수 있습니다):
/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
// 0 and 1 are not prime numbers
if (test == 0 || test == 1) return false;
// 2 and 3 are prime numbers
if (test == 2) return true;
// all even numbers, save 2, are not prime
if (test % 2 == 0) return false;
double squared = Math.Sqrt(test);
int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));
// start with 5, make increments of 2, even numbers do not need to be tested
for (int idx = 3; idx < flooredAndSquared; idx++)
{
if (test % idx == 0)
{
return false;
}
}
return true;
}
나는 제곱 부분이 실패한다는 것을 알고 있습니다(또는 실패합니다). Math.Ceiling도 시도했지만 거의 동일한 결과가 나왔습니다.
해결책
안타깝게도 저는 이전에 알고리즘적 접근 방식을 시도해 본 적이 없습니다.그러나 접근 방식을 효율적으로 구현하려면 캐싱을 수행하는 것이 좋습니다.정의된 임계값보다 작은 모든 소수를 저장하는 배열을 만들고, 이 배열을 채우고, 그 안에서 검색하거나 사용합니다.
다음 예에서 숫자가 소수인지 확인하는 것은 가장 좋은 경우(즉, 숫자가 다음보다 작거나 같을 때) O(1)입니다. maxPrime, 64K 버퍼의 경우 821,461), 다른 경우에는 다소 최적화되어 있습니다(처음 820,000개 중 64K 숫자에 대해서만 mod를 확인하여 약 8%).
(메모:이 답변을 "최적" 접근 방식으로 받아들이지 마십시오.구현을 최적화하는 방법에 대한 더 많은 예입니다.)
public static class PrimeChecker
{
private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB
private static int[] primes;
public static int MaxPrime { get; private set; }
public static bool IsPrime(int value)
{
if (value <= MaxPrime)
{
return Array.BinarySearch(primes, value) >= 0;
}
else
{
return IsPrime(value, primes.Length) && IsLargerPrime(value);
}
}
static PrimeChecker()
{
primes = new int[BufferSize];
primes[0] = 2;
for (int i = 1, x = 3; i < primes.Length; x += 2)
{
if (IsPrime(x, i))
primes[i++] = x;
}
MaxPrime = primes[primes.Length - 1];
}
private static bool IsPrime(int value, int primesLength)
{
for (int i = 0; i < primesLength; ++i)
{
if (value % primes[i] == 0)
return false;
}
return true;
}
private static bool IsLargerPrime(int value)
{
int max = (int)Math.Sqrt(value);
for (int i = MaxPrime + 2; i <= max; i += 2)
{
if (value % i == 0)
return false;
}
return true;
}
}
다른 팁
나는 이것이 당신의 문제라고 생각합니다.
for (int idx = 3; idx < flooredAndSquared; idx++)
이것은
for (int idx = 3; idx <= flooredAndSquared; idx++)
그래서 제곱수를 소수로 얻지 못합니다.또한 "idx++" 대신 "idx += 2"를 사용할 수 있습니다. 왜냐하면 홀수만 테스트하면 되기 때문입니다(바로 위의 주석에 쓴 것처럼...).
이것이 당신이 찾고 있는 것인지는 모르겠지만 속도에 대해 정말로 관심이 있다면 체를 사용하는 대신 소수성을 테스트하기 위한 확률적 방법을 조사해야 합니다. 라빈-밀러 Mathematica에서 사용하는 확률적 소수성 테스트입니다.
여기에 소수를 계산하기 위해 체 또는 에라토스테네스를 사용하는 클래스를 게시했습니다.
Mark가 말했듯이 Miller-Rabin 테스트는 실제로 매우 좋은 방법입니다.추가 참조(의사 코드 포함)는 다음과 같습니다. 위키피디아 기사 그것에 대해.
확률론적이지만 매우 적은 수의 사례만 테스트하여 숫자가 int(및 거의 긴) 범위의 숫자에 대해 소수인지 여부를 결정할 수 있다는 점에 유의해야 합니다.보다 Wikipedia 기사의 이 부분, 또는 원시성 증명 참조 상세 사항은.
나는 또한 읽기를 권하고 싶다. 이 기사 모듈러 지수화에서는 그렇지 않으면 Miller-Rabin 테스트를 수행하려고 할 때 매우 큰 숫자를 처리하게 될 것입니다...
당신은 조사하고 싶을 수도 있습니다 페르마의 작은 정리.
다음은 책에 나온 의사 코드입니다. S의 알고리즘다스굽타, C.H.Papadimitriou 및 U.V.바지라니, 여기서 n은 소수성을 테스트하는 숫자입니다.
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
페르마의 정리를 구현하는 것은 체 솔루션보다 더 빠릅니다.그러나 페르마의 검정을 통과하지만 소수가 아닌 카마이클 수가 있습니다.이에 대한 해결 방법이 있습니다.상담을 추천드려요 앞서 언급한 책의 섹션 1.3.이는 소수성 테스트에 관한 것이며 도움이 될 수 있습니다.
이 시도...
if (testVal == 2) return true;
if (testVal % 2 == 0) return false;
for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
if (testVal % i == 0)
return false;
}
return true;
이거 꽤 여러번 써봤는데..체만큼 빠르진 않네요..하지만 작동합니다.
다음은 오일러 중 하나를 풀기 위해 작성한 중간 정도의 괜찮은 함수입니다.
private static long IsPrime(long input)
{
if ((input % 2) == 0)
{
return 2;
}
else if ((input == 1))
{
return 1;
}
else
{
long threshold = (Convert.ToInt64(Math.Sqrt(input)));
long tryDivide = 3;
while (tryDivide < threshold)
{
if ((input % tryDivide) == 0)
{
Console.WriteLine("Found a factor: " + tryDivide);
return tryDivide;
}
tryDivide += 2;
}
Console.WriteLine("Found a factor: " + input);
return -1;
}
}
소수를 확인하는 빠른 알고리즘이 있습니다.2와 3을 제외한 소수가 6k ± 1의 형태라는 것을 알면 알고리즘을 개선할 수 있습니다.따라서 먼저 입력이 2 또는 3으로 나누어지는지 테스트할 수 있습니다.그런 다음 6k ± 1 ≤ √ 형식의 숫자가 모두 입력되었는지 확인합니다.
bool IsPrime(int input)
{
//2 and 3 are primes
if (input == 2 || input == 3)
return true;
else if (input % 2 == 0 || input % 3 == 0)
return false; //Is divisible by 2 or 3?
else
{
for (int i = 5; i * i <= input; i += 6)
{
if (input % i == 0 || input % (i + 2) == 0)
return false;
}
return true;
}
}
시도해 보세요 에라토스테네스의 체 -- 루트 및 부동 소수점 문제를 해결해야 합니다.
에 관해서는 floor, 귀하는 다음을 수강함으로써 더 나은 서비스를 받을 수 있습니다. ceiling.
private static bool IsPrime(int number) {
if (number <= 3)
return true;
if ((number & 1) == 0)
return false;
int x = (int)Math.Sqrt(number) + 1;
for (int i = 3; i < x; i += 2) {
if ((number % i) == 0)
return false;
}
return true;
}
더 빨리 못 구해요...
나는 생각했다 소수 및 소수성 테스트 유용했으며 AKS 알고리즘은 아마도 기반 테스트에 비해 특별히 실용적이지는 않더라도 흥미로워 보입니다.
이것은 소수 테스트에 매우 빠르게 작동합니다(vb.net).
Dim rnd As New Random()
Const one = 1UL
Function IsPrime(ByVal n As ULong) As Boolean
If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then
return false
End If
Dim s = n - one
While s Mod 2 = 0
s >>= one
End While
For i = 0 To 10 - 1
Dim a = CULng(rnd.NextDouble * n + 1)
Dim temp = s
Dim m = Numerics.BigInteger.ModPow(a, s, n)
While temp <> n - one AndAlso m <> one AndAlso m <> n - one
m = (m * m) Mod n
temp = temp * 2UL
End While
If m <> n - one AndAlso temp Mod 2 = 0 Then
Return False
End If
Next i
Return True
End Function
다른 사람이 관심이 있는 경우를 대비해 위의 Mohammad의 절차를 VBA로 변환했습니다.1, 0, 음수가 모두 소수가 아닌 것으로 정의되어 있으므로 제외하는 검사를 추가했습니다.
Excel VBA에서만 이것을 테스트했습니다.
Function IsPrime(input_num As Long) As Boolean
Dim i As Long
If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime.
IsPrime = False: Exit Function
ElseIf input_num = 2 Then
IsPrime = True: Exit Function '2 is a prime
ElseIf input_num = 3 Then
IsPrime = True: Exit Function '3 is a prime.
ElseIf input_num Mod 2 = 0 Then
IsPrime = False: Exit Function 'divisible by 2, so not a prime.
ElseIf input_num Mod 3 = 0 Then
IsPrime = False: Exit Function 'divisible by 3, so not a prime.
Else
'from here on, we only need to check for factors where
'6k ± 1 = square root of input_num:
i = 5
Do While i * i <= input_num
If input_num Mod i = 0 Then
IsPrime = False: Exit Function
ElseIf input_num Mod (i + 2) = 0 Then
IsPrime = False: Exit Function
End If
i = i + 6
Loop
IsPrime = True
End If
End Function
for 루프는 다음과 같아야 합니다.
for (int idx = 3; idx * idx <= test; idx++) { ... }
이렇게 하면 부동 소수점 계산을 피할 수 있습니다.더 빠르게 실행해야 더 정확할 것입니다.이것이 바로 for 조건문은 단순히 부울 표현식입니다.이런 일이 가능해집니다.
