¿Existe un algoritmo simple que pueda determinar si X es primo y no confundir a un simple programador mortal?
https://stackoverflow.com/questions/188425
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
He intentado abrirme camino a través del Proyecto Euler y he notado que un puñado de problemas te piden que determines un número primo como parte de él.
-
Sé que puedo dividir x por 2, 3, 4, 5, ..., raíz cuadrada de X y si llego a la raíz cuadrada, puedo (con seguridad) asumir que el número es primo . Lamentablemente, esta solución parece bastante difícil.
-
He buscado mejores algoritmos sobre cómo determinar si un número es primo, pero me confundo rápidamente.
¿Existe un algoritmo simple que pueda determinar si X es primo y no confundir a un simple programador mortal?
¡Muchas gracias!
Solución
El primer algoritmo es bastante bueno y se usó mucho en el Proyecto Euler. Si conoce el número máximo que desea, también puede investigar el tamiz de Eratóstenes.
Si mantiene la lista de primos, también puede refinar el primer algoritmo para dividir solo con primos hasta la raíz cuadrada del número.
Con estos dos algoritmos (dividiendo y el tamiz) debería poder resolver los problemas.
Editar : nombre fijo como se indica en los comentarios
Otros consejos
Para generar todos los números primos menores que un límite Tamiz de Eratóstenes (la página contiene variantes en 20 lenguajes de programación) es la solución más antigua y más simple.
En Python:
def iprimes_upto(limit):
is_prime = [True] * limit
for n in range(2, limit):
if is_prime[n]:
yield n
for i in range(n*n, limit, n): # start at ``n`` squared
is_prime[i] = False
Ejemplo:
>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
Veo que la prueba de primalidad de Fermat ya se ha sugerido, pero he estado trabajando en Estructura e interpretación de programas de computadora , y también le dan el Miller-Rabin prueba (ver Sección 1.2.6, problema 1.28) como otra alternativa. Lo he estado usando con éxito para los problemas de Euler.
Aquí hay una optimización simple de su método que no es exactamente el Tamiz de Eratóstenes pero es muy fácil de implementar: primero intente dividir X entre 2 y 3, luego haga un bucle sobre j = 1..sqrt (X) / 6, tratando de dividir entre 6 * j-1 y 6 * j + 1. Esto omite automáticamente todos los números divisibles por 2 o 3, obteniendo una aceleración de factor constante bastante agradable.
Teniendo en cuenta los siguientes hechos (de MathsChallenge.net ) :
- Todos los números primos excepto 2 son impares.
- Todos los primos mayores que 3 se pueden escribir en la forma 6k - 1 o 6k + 1.
- No necesita verificar más allá de la raíz cuadrada de n
Aquí está la función C ++ que uso para n relativamente pequeño:
bool isPrime(unsigned long n)
{
if (n == 1) return false; // 1 is not prime
if (n < 4) return true; // 2 and 3 are both prime
if ((n % 2) == 0) return false; // exclude even numbers
if (n < 9) return true; //we have already excluded 4, 6, and 8.
if ((n % 3) == 0) return false; // exclude remaining multiples of 3
unsigned long r = floor( sqrt(n) );
unsigned long f = 5;
while (f <= r)
{
if ((n % f) == 0) return false;
if ((n % (f + 2)) == 0) return false;
f = f + 6;
}
return true; // (in all other cases)
}
Probablemente podría pensar en más optimizaciones propias.
Recomiendo Prueba de primalidad de Fermat . Es una prueba probabilística, pero es correcta sorprendentemente a menudo. Y es increíblemente rápido en comparación con el tamiz.
Para números razonablemente pequeños, x% n para hasta sqrt (x) es terriblemente rápido y fácil de codificar.
Mejoras simples:
prueba 2 y números impares solamente.
prueba 2, 3 y múltiplos de 6 + o - 1 (todos los números primos que no sean 2 o 3 son múltiplos de 6 +/- 1, por lo que básicamente omite todos los números pares y todos los múltiplos de 3
prueba solo números primos (requiere calcular o almacenar todos los números primos hasta sqrt (x))
Puede usar el método de tamizado para generar rápidamente una lista de todos los números primos hasta cierto límite arbitrario, pero tiende a consumir mucha memoria. Puede usar los trucos de múltiplos de 6 para reducir el uso de memoria a 1/3 de bit por número.
Escribí una clase principal simple (C #) que usa dos campos de bits para múltiplos de 6 + 1 y múltiplos de 6-1, luego realiza una búsqueda simple ... y si el número que estoy probando está fuera de los límites de el tamiz, luego se vuelve a probar en 2, 3 y múltiplos de 6 +/- 1. Descubrí que generar un tamiz grande en realidad lleva más tiempo que calcular primos sobre la marcha para la mayoría de los problemas de Euler que he resuelto hasta aquí. ¡El principio KISS ataca de nuevo!
Escribí una clase principal que usa un tamiz para calcular previamente los números primos más pequeños, luego se basa en pruebas de 2, 3 y múltiplos de seis +/- 1 para los que están fuera del rango del tamiz.
Para el Proyecto Euler, tener una lista de números primos es realmente esencial. Sugeriría mantener una lista que use para cada problema.
Creo que lo que estás buscando es el Tamiz de Eratóstenes .
Tu derecho, el más simple es el más lento. Puedes optimizarlo un poco.
Considere el uso del módulo en lugar de las raíces cuadradas. Mantenga un registro de sus primos. solo necesita dividir 7 entre 2, 3 y 5 ya que 6 es un múltiplo de 2 y 3, y 4 es un múltiplo de 2.
Rslite mencionó el eranthenos sieve . Es bastante sencillo. Lo tengo en varios idiomas en casa. Agregue un comentario si desea que publique ese código más tarde.
Aquí está mi C ++. Tiene mucho espacio para mejorar, pero es rápido en comparación con las versiones de idiomas dinámicos.
// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>
int main(void) {
// using unsigned short.
// maximum value is around 65000
const unsigned short max = 50000;
unsigned short x[max];
for(unsigned short i = 0; i < max; i++)
x[i] = i + 2;
for(unsigned short outer = 0; outer < max; outer++) {
if( x[outer] == 0)
continue;
unsigned short item = x[outer];
for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
unsigned int searchvalue = item * multiplier;
unsigned int maxValue = max + 1;
for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
if(x[maxIndex] != 0) {
maxValue = x[maxIndex];
break;
}
}
for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
if( searchvalue > maxValue )
break;
if( x[searchindex] == searchvalue ) {
x[searchindex] = 0;
break;
}
}
}
}
for(unsigned short printindex = 0; printindex < max; printindex++) {
if(x[printindex] != 0)
std::cout << x[printindex] << "\t";
}
return 0;
}
Lanzaré el código de Perl y Python que tengo tan pronto como lo encuentre. Son similares en estilo, solo que menos líneas.
Aquí hay una prueba de primalidad simple en D (Marte Digital):
/**
* to compile:
* $ dmd -run prime_trial.d
* to optimize:
* $ dmd -O -inline -release prime_trial.d
*/
module prime_trial;
import std.conv : to;
import std.stdio : w = writeln;
/// Adapted from: http://www.devx.com/vb2themax/Tip/19051
bool
isprime(Integer)(in Integer number)
{
/* manually test 1, 2, 3 and multiples of 2 and 3 */
if (number == 2 || number == 3)
return true;
else if (number < 2 || number % 2 == 0 || number % 3 == 0)
return false;
/* we can now avoid to consider multiples
* of 2 and 3. This can be done really simply
* by starting at 5 and incrementing by 2 and 4
* alternatively, that is:
* 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
* we don't need to go higher than the square root of the number */
for (Integer divisor = 5, increment = 2; divisor*divisor <= number;
divisor += increment, increment = 6 - increment)
if (number % divisor == 0)
return false;
return true; // if we get here, the number is prime
}
/// print all prime numbers less then a given limit
void main(char[][] args)
{
const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
for (uint i = 0; i < limit; ++i)
if (isprime(i))
w(i);
}
También estoy trabajando a través de los problemas del Proyecto Euler y, de hecho, acabo de terminar # 3 (por id), que es la búsqueda del factor primo más alto de un número compuesto (el número en el? es 600851475143).
Miré toda la información sobre los primos (las técnicas de tamizado ya mencionadas aquí), y sobre la factorización de enteros en Wikipedia y se me ocurrió un algoritmo de división de prueba de fuerza bruta que decidí que haría.
Entonces, cuando estoy haciendo los problemas de euler para aprender rubí, estaba buscando codificar mi algoritmo y me topé con la biblioteca matemática que tiene un Clase principal y una Clase entera con un método prime_division . cuan genial es eso. pude obtener la respuesta correcta al problema con este fragmento de rubí:
require "mathn.rb"
puts 600851475143.prime_division.last.first
este fragmento genera la respuesta correcta a la consola. Por supuesto, terminé leyendo y aprendiendo un montón antes de encontrarme con esta pequeña belleza, solo pensé en compartirla con todos ...
Me gusta este código de Python.
def primes(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
return [j for j in xrange(2, limit) if x[j] == 1]
Una variante de esto puede usarse para generar los factores de un número.
def factors(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
result = []
y = limit-1
while x[y] != 1 :
divisor = x[y]
result.append(divisor)
y /= divisor
result.append(y)
return result
Por supuesto, si factorizara un lote de números, no volvería a calcular el caché; Lo haría una vez y buscaría en él.
No está optimizado pero es una función muy simple.
function isprime(number){
if (number == 1)
return false;
var times = 0;
for (var i = 1; i <= number; i++){
if(number % i == 0){
times ++;
}
}
if (times > 2){
return false;
}
return true;
}
Quizás esta implementación en Java pueda ser útil:
public class SieveOfEratosthenes {
/**
* Calling this method with argument 7 will return: true true false false true false true false
* which must be interpreted as : 0 is NOT prime, 1 is NOT prime, 2 IS prime, 3 IS prime, 4 is NOT prime
* 5 is prime, 6 is NOT prime, 7 is prime.
* Caller may either revert the array for easier reading, count the number of primes or extract the prime values
* by looping.
* @param upTo Find prime numbers up to this value. Must be a positive integer.
* @return a boolean array where index represents the integer value and value at index returns
* if the number is NOT prime or not.
*/
public static boolean[] isIndexNotPrime(int upTo) {
if (upTo < 2) {
return new boolean[0];
}
// 0-index array, upper limit must be upTo + 1
final boolean[] isIndexNotPrime = new boolean[upTo + 1];
isIndexNotPrime[0] = true; // 0 is not a prime number.
isIndexNotPrime[1] = true; // 1 is not a prime number.
// Find all non primes starting from 2 by finding 2 * 2, 2 * 3, 2 * 4 until 2 * multiplier > isIndexNotPrime.len
// Find next by 3 * 3 (since 2 * 3 was found before), 3 * 4, 3 * 5 until 3 * multiplier > isIndexNotPrime.len
// Move to 4, since isIndexNotPrime[4] is already True (not prime) no need to loop..
// Move to 5, 5 * 5, (2 * 5 and 3 * 5 was already set to True..) until 5 * multiplier > isIndexNotPrime.len
// Repeat process until i * i > isIndexNotPrime.len.
// Assume we are looking up to 100. Break once you reach 11 since 11 * 11 == 121 and we are not interested in
// primes above 121..
for (int i = 2; i < isIndexNotPrime.length; i++) {
if (i * i >= isIndexNotPrime.length) {
break;
}
if (isIndexNotPrime[i]) {
continue;
}
int multiplier = i;
while (i * multiplier < isIndexNotPrime.length) {
isIndexNotPrime[i * multiplier] = true;
multiplier++;
}
}
return isIndexNotPrime;
}
public static void main(String[] args) {
final boolean[] indexNotPrime = SieveOfEratosthenes.isIndexNotPrime(7);
assert !indexNotPrime[2]; // Not (not prime)
assert !indexNotPrime[3]; // Not (not prime)
assert indexNotPrime[4]; // (not prime)
assert !indexNotPrime[5]; // Not (not prime)
assert indexNotPrime[6]; // (not prime)
assert !indexNotPrime[7]; // Not (not prime)
}
}
El algoritmo de prueba principal de AKS:
Input: Integer n > 1
if (n is has the form ab with b > 1) then output COMPOSITE
r := 2
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE
if (r is prime greater than 2) then {
let q be the largest factor of r-1
if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break
}
r := r+1
}
for a = 1 to 2sqrt(r)log n {
if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE
}
output PRIME;
otra forma en python es:
import math
def main():
count = 1
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 2
if __name__ == '__main__':
main()
