¿Cómo puedo probar la primalidad?
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy escribiendo una pequeña biblioteca con algunos métodos relacionados con números primos. Como he hecho el trabajo preliminar (también conocido como métodos de trabajo) y ahora estoy buscando algo de optimización. Por supuesto, Internet es un excelente lugar para hacerlo. Sin embargo, me topé con un problema de redondeo y me preguntaba cómo resolverlo.
En el bucle que uso para probar un número por su primalidad, es más eficiente buscar hasta sqrt (n) en lugar de n / 2 o incluso n - 1. Pero debido a problemas de redondeo, algunos números se omiten y, por lo tanto, algunos números primos se omiten omitido! Por ejemplo, la prima número 10000 debería ser: 104729, pero la versión 'optimizada' termina con: 103811.
Algún código (está abierto para una mayor optimización, lo sé, pero solo puedo manejar una cosa a la 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;
}
Sé que la parte cuadrada me falla (o fallo), probé Math.Ceiling también, con aproximadamente los mismos resultados.
Solución
Lamentablemente, no he probado los enfoques algorítmicos antes. Pero si desea implementar su enfoque de manera eficiente, le sugiero que haga un poco de almacenamiento en caché. Cree una matriz para almacenar todos los números primos por debajo de un umbral definido, complete esta matriz y busque dentro de / utilizándola.
En el siguiente ejemplo, encontrar si un número es primo es O (1) en el mejor de los casos (es decir, cuando el número es menor o igual que maxPrime , que es 821,461 para un 64K buffer), y está algo optimizado para otros casos (al marcar mod sobre solo 64K números de los primeros 820,000 - aproximadamente 8%).
(Nota: No tome esta respuesta como el enfoque "óptimo". Es más un ejemplo de cómo optimizar su implementación.)
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;
}
}
Otros consejos
Creo que este es tu problema:
for (int idx = 3; idx < flooredAndSquared; idx++)
Esto debería ser
for (int idx = 3; idx <= flooredAndSquared; idx++)
para que no obtenga números cuadrados como primos. Además, puede usar " idx + = 2 " en lugar de " idx ++ " porque solo tienes que probar números impares (como escribiste en el comentario directamente arriba ...).
No sé si esto es lo que estás buscando, pero si realmente te preocupa la velocidad, entonces deberías buscar métodos probablísticos para probar la primalidad en lugar de usar un tamiz. Rabin-Miller es una prueba de primitiva probabilística utilizada por Mathematica.
Publiqué una clase que usa el tamiz o Eratóstenes para calcular los números primos aquí:
¿El tamaño de una matriz está limitado por el límite superior de int (2147483647)?
Como dijo Mark, la prueba de Miller-Rabin es en realidad un muy buen camino a seguir. Una referencia adicional (con pseudocódigo) es el artículo de Wikipedia sobre
Debe tenerse en cuenta que si bien es probabilístico, al probar solo un número muy pequeño de casos, puede determinar si un número es primo para los números en el rango int (y casi largo). Consulte esta parte de ese artículo de Wikipedia , o la referencia de Primality Proving para más detalles.
También recomendaría leer este artículo sobre exponenciación modular, de lo contrario, irá tratar con números muy muy grandes al intentar hacer la prueba de Miller-Rabin ...
Es posible que desee consultar el pequeño teorema de Fermat .
Aquí está el pseudocódigo del libro Algoritmos de S. Dasgupta, C.H. Papadimitriou y U.V. Vazirani , donde n es el número que está probando para primalidad.
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
La implementación del teorema de Fermat debería ser más rápida que la solución del tamiz. Sin embargo, hay números de Carmichael que pasan la prueba de Fermat y NO son primos. Hay soluciones para esto. Recomiendo consultar la Sección 1.3 en el libro mencionado anteriormente . Se trata de pruebas de primalidad y puede ser útil para usted.
Prueba esto ...
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;
Lo he usado varias veces ... No es tan rápido como un tamiz ... pero funciona.
Aquí hay una función decente a mitad de camino que escribí para resolver uno de los 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;
}
}
Tengo un algoritmo rápido para verificar números primos. Puede mejorar su algoritmo si sabe que los primos tienen la forma 6k & # 177; 1, con la excepción de 2 y 3. Entonces, primero puede probar si la entrada es divisible por 2 o 3. Luego, verifique todos los números de la forma 6k & # 177; 1 & # 8804; & # 8730; entrada.
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;
}
}
Pruebe el tamiz de eratóstenes , que debería eliminar la obtención de la raíz y el punto flotante problemas.
En cuanto al piso , será mejor que tome el techo .
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;
}
No puedo obtenerlo más rápido ...
Pensé Números primos y pruebas de primalidad fue útil y el algoritmo AKS suena interesante incluso si no es particularmente práctico en comparación con las pruebas basadas en probabilidad.
Esto funciona muy rápido para probar primos (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
En caso de que alguien más esté interesado, aquí está mi conversión del procedimiento de Mohammad anterior a VBA. Agregué un cheque para excluir 1, 0 y números negativos, ya que todos están definidos como no primos.
Solo he probado esto en 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
Su bucle for debería verse así:
for (int idx = 3; idx * idx <= test; idx++) { ... }
De esa manera, evita el cálculo de punto flotante. Debería correr más rápido y será más preciso. Esta es la razón por la cual la instrucción for condicional es simplemente una expresión booleana: hace posible cosas como esta.
