Como posso testar para primalidade?
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou escrevendo uma pequena biblioteca com alguns métodos número primo relacionados. Como eu fiz o trabalho de base (métodos aka de trabalho) e agora estou procurando alguma otimização. Claro que a internet é um excelente lugar para fazê-lo. Eu, porém, tropeçou em um problema de arredondamento e eu queria saber como resolver isto.
No circuito que eu uso para testar um número para ele é primality é mais eficiente para pesquisar até sqrt (n) em vez de n / 2 ou mesmo n - 1. Mas devido a problemas de arredondamento algum número get ignorados e, portanto, alguns primos são ignorados! Por exemplo, o primeiro-10000 deve ser: 104729, mas a versão 'otimizado' termina com:. 103811
Alguns códigos (é aberta por mais de otimização, eu sei, mas eu posso lidar com apenas uma coisa de cada vez):
/// <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;
}
Eu sei que a parte quadrado me falha (ou eu falhar), tentou Math.Ceiling, bem como, com os mesmos resultados.
Solução
Infelizmente, eu não tentei as abordagens algorítmicos antes. Mas se você quiser implementar sua abordagem de forma eficiente, eu sugiro fazer alguns cache. Criar uma matriz para armazenar todos os números primos menos de um limite definido, preencher esta matriz, e procurar dentro / usá-lo.
No exemplo a seguir, encontrando se um número é primordial é O (1) no melhor caso (ou seja, quando o número é menor do que ou igual a maxPrime, que é 821.461 para uma memória intermédia 64 K), e é um pouco optimizada para outros casos (por verificação mod mais única 64K números fora do primeiro 820.000 - cerca de 8%).
(Nota:.. Não tome essa resposta como a abordagem "ideal" É mais um exemplo sobre como otimizar sua implementação)
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;
}
}
Outras dicas
Eu acho que este é o problema:
for (int idx = 3; idx < flooredAndSquared; idx++)
Esta deve ser
for (int idx = 3; idx <= flooredAndSquared; idx++)
para que você não obter números quadrados como primos. Além disso, você pode usar "idx + = 2" em vez de "idx ++" porque você só tem que testar números ímpares (como você escreveu no comentário diretamente acima ...).
Eu não sei se isso é exatamente o que você está procurando, mas se você está realmente preocupado com a velocidade, então você deve olhar para métodos probablistic para testar primalidade ao invés de usar uma peneira. Rabin-Miller é um teste de primalidade probabilística usado por Mathematica.
Eu postei uma classe que usa a peneira ou Eratóstenes para calcular números primos aqui:
é o tamanho de uma matriz limitado pelo limite superior de int (2147483647)?
Como Mark disse, o teste de Miller-Rabin é realmente um bom caminho a percorrer. Uma referência adicional (com pseudo-código) é o Wikipedia sobre -lo.
Deve-se notar que, embora seja probabilística, testando apenas um número muito pequeno de casos, você pode determinar se um número é primo para números na int (e quase de comprimento) gama. Consulte esta parte desse artigo Wikipedia , ou o Primality Provando referência para mais detalhes.
Eu também recomendo a leitura este artigo em exponenciação modular, caso contrário você vai estar lidando com muito, muito grandes números quando se tenta fazer o teste de Miller-Rabin ...
Você pode querer olhar para pouco de Fermat teorema .
Aqui está o código pseudo do livro Algoritmos de S. Dasgupta, C. H. Papadimitriou, e luz U.V. Vazirani , onde n é o número que está a testar para primalidade.
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
O teorema de Fermat Implementação deve ser mais rápido, então a solução peneira. No entanto, há um número Carmichael que passam o teste de Fermat e não são prime. Existem soluções para este. Eu recomendo consultar Seção 1.3 no livro supra citados . É tudo sobre o teste de primalidade e pode ser útil para você.
Tente isto ...
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;
Ive usou este algumas vezes .. não tão rápido como uma peneira .. mas funciona.
Aqui está uma função decente eu escrevi para resolver um dos Euler:
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;
}
}
Eu tenho um algoritmo rápido para verificação de números primos. Você pode melhorar o seu algoritmo se você sabe que primos são na forma 6k ± 1, com exceção de 2 e 3. Então, primeiro você pode testar se a entrada é divisível por 2 ou 3. Em seguida, verificar todos os números de forma 6k ± 1 = vinput.
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;
}
}
Tente o Crivo de Eratóstenes - que deve tirar recebendo a raiz e ponto flutuante questões.
Quanto ao floor, você estará melhor servido por tomar o 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;
}
Eu não posso obtê-lo mais rápido ...
Prime números e testes primality foi útil e os AKS algoritmo parece interessante, mesmo se não é particularmente prático comparado a um testes baseados probabily.
Isso funciona muito rápido para testar primes (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
No caso de alguém mais está interessado, aqui está a minha conversão do procedimento de Mohammad acima para VBA. Eu adicionei uma seleção para excluir 1, 0 e negativos números como eles são todos definidos como não prime.
Eu só testei isso no 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
Seu loop deve ficar assim:
for (int idx = 3; idx * idx <= test; idx++) { ... }
Dessa forma, você evita de ponto flutuante computação. Deve correr mais rápido e vai ser mais exato. É por isso que a condicional declaração for é simplesmente uma expressão booleana: faz coisas como esta possível
