algorithm - son - ¿Cuál es el mejor algoritmo para verificar si un número es primo?

numeros primos

Question

Solo un ejemplo de lo que estoy buscando: podría representar cada número impar con un bit, por ejemplo, para el rango de números dado (1, 10), comienza en 3:

1110

El siguiente diccionario se puede exprimir más ¿no? Podría eliminar múltiplos de cinco con algún trabajo, pero los números que terminan con 1, 3, 7 o 9 deben estar allí en la matriz de bits. Espero que esto aclare lo que quiero.

Estoy buscando el mejor algoritmo, para verificar si un número es primordial, es decir, una función booleana:

bool isprime(number);

Me gustaría saber el mejor algoritmo para implementar esta funcionalidad. Naturalmente, habría una estructura de datos que podría consultar. Defino el mejor algoritmo , que es el algoritmo que produce una estructura de datos con el menor consumo de memoria para el rango (1, N), donde N es una constante.

Answer 1

Para saber si el número o los números en un rango son / son primos.

#!usr/bin/python3

def prime_check(*args):
    for arg in args:
        if arg > 1:     # prime numbers are greater than 1
            for i in range(2,arg):   # check for factors
                if(arg % i) == 0:
                    print(arg,"is not Prime")
                    print(i,"times",arg//i,"is",arg)
                    break
            else:
                print(arg,"is Prime")

            # if input number is less than
            # or equal to 1, it is not prime
        else:
            print(arg,"is not Prime")
    return

# Calling Now
prime_check(*list(range(101)))  # This will check all the numbers in range 0 to 100 
prime_check(#anynumber)         # Put any number while calling it will check.

Answer 2

Creo que uno de los más rápidos es mi método que hice.

void prime(long long int number) {
    // Establishing Variables
    long long int i = 5;
    int w = 2;
    const long long int lim = sqrt(number);

    // Gets 2 and 3 out of the way
    if (number == 1) { cout << number << " is hard to classify. /n";  return; }
    if (number == 2) { cout << number << " is Prime. /n";  return; }
    if (number == 3) { cout << number << " is Prime. /n";  return; }

    // Tests Odd Ball Factors
    if (number % 2 == 0) { cout << number << " is not Prime. /n";  return; }
    if (number % 3 == 0) { cout << number << " is not Prime. /n";  return; }

    while (i <= lim) {
        if (number % i == 0) { cout << number << " is not Prime. /n";  return; }
        // Tests Number
        i = i + w; // Increments number
        w = 6 - i; // We already tested 2 and 3
        // So this removes testing multepules of this
    }
    cout << number << " is Prime. /n"; return;
}

Answer 3

Demasiado tarde para la fiesta, pero espero que esto ayude. Esto es relevante si estás buscando grandes números primos:

Para probar números impares grandes, debe usar la prueba Fermat y / o la prueba Miller-Rabin.

Estas pruebas usan una exponenciación modular que es bastante costosa, para la exponenciación de n bits se necesita al menos n una multiplicación grande y n gran división interna. Lo que significa que la complejidad de la exponenciación modular es O (n³).

Entonces, antes de usar las armas grandes, debes hacer bastantes divisiones de prueba. Pero no lo hagas ingenuamente, hay una forma de hacerlo rápido. Primero multiplica tantos primos juntos como tantos ajustes en las palabras que usas para los enteros grandes. Si usa palabras de 32 bits, multiplique 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615 y calcule el mayor divisor común con el número que prueba usando el algoritmo euclidiano. Después del primer paso, el número se reduce por debajo del tamaño de la palabra y continúa el algoritmo sin realizar divisiones enteras grandes y completas. Si el GCD! = 1, eso significa que uno de los números primos que multiplicaste juntos divide el número, por lo que tienes una prueba de que no es primo. Luego continúe con 31 * 37 * 41 * 43 * 47 = 95041567, y así sucesivamente.

Una vez que haya probado varios cientos (o miles) de primos de esta forma, puede hacer 40 rondas de la prueba de Miller-Rabin para confirmar que el número es primordial, después de 40 rondas puede estar seguro de que el número es primo; solo hay 2 ^ -80 de posibilidades de que sea no (es más probable que su hardware no funcione correctamente ...).

Answer 4

El algoritmo más rápido para la prueba de primo general es AKS . El artículo de Wikipedia lo describe extensamente y enlaces al documento original.

Si quieres encontrar números grandes, mira en primos que tienen formas especiales como primos de Mersenne .

El algoritmo que generalmente implemento (fácil de entender y codificar) es el siguiente (en Python):

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

Es una variante del clásico algoritmo O(sqrt(N)) . Utiliza el hecho de que un primo (excepto 2 y 3) tiene la forma 6k - 1 o 6k + 1 y solo mira los divisores de esta forma.

A veces, si realmente quiero velocidad y el rango es limitado , implemento una prueba de pseudoprima basada en el pequeño teorema de Fermat . Si realmente quiero más velocidad (es decir, evito el algoritmo O (sqrt (N)) por completo), precomputo los falsos positivos (vea los números de Carmichael ) y realizo una búsqueda binaria. Esta es, de lejos, la prueba más rápida que he implementado, el único inconveniente es que el alcance es limitado.

Answer 5

El mejor método, en mi opinión, es usar lo que se ha ido antes.

Hay listas de los primeros N primos en Internet con N extendiéndose hasta por lo menos cincuenta millones . Descarga los archivos y úsalos, es probable que sea mucho más rápido que cualquier otro método que se te ocurra.

Si desea un algoritmo real para hacer sus propios números primos, Wikipedia tiene todo tipo de cosas buenas en los números primos here , incluidos enlaces a los diversos métodos para hacerlo, y las pruebas principales aquí , ambos métodos basados ​​en la probabilidad y deterministas rápidos.

Debería haber un esfuerzo concertado para encontrar los primeros mil millones (o incluso más) de números primos y publicarlos en la red en alguna parte para que la gente pueda dejar de hacer este mismo trabajo una y otra vez y ... :-)

Answer 6

En Python:

def is_prime(n):
    return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))

Una conversión más directa del formalismo matemático a Python usaría todo (n% p! = 0 ...) , pero eso requiere una evaluación estricta de todos los valores de p. La versión no puede finalizar anticipadamente si se encuentra un valor True.

Answer 7

Hay muchas maneras de hacer la prueba de primalidad .

Realmente no hay una estructura de datos para que usted pueda consultar. Si tiene muchos números para evaluar, probablemente debería ejecutar una prueba probabilística ya que estos son más rápidos, y luego hacer un seguimiento con una prueba determinista para asegurarse de que el número sea primo.

Debe saber que la matemática detrás de los algoritmos más rápidos no es para los débiles de corazón.

Answer 8

Idea similar al algoritmo AKS que se ha mencionado

public static boolean isPrime(int n) {

    if(n == 2 || n == 3) return true;
    if((n & 1 ) == 0 || n % 3 == 0) return false;
    int limit = (int)Math.sqrt(n) + 1;
    for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
        if(n % i == 0) return false;
        numChecks++;
    }
    return true;
}

Answer 9

Memoria más pequeña? Esto no es el más pequeño, pero es un paso en la dirección correcta.

class PrimeDictionary {
    BitArray bits;

    public PrimeDictionary(int n) {
        bits = new BitArray(n + 1);
        for (int i = 0; 2 * i + 3 <= n; i++) {
            bits.Set(i, CheckPrimality(2 * i + 3));
        }
    }

    public PrimeDictionary(IEnumerable<int> primes) {
        bits = new BitArray(primes.Max());
        foreach(var prime in primes.Where(p => p != 2)) {
            bits.Set((prime - 3) / 2, true);
        }
    }

    public bool IsPrime(int k) {
        if (k == 2) {
            return true;
        }
        if (k % 2 == 0) {
            return false;
        }
        return bits[(k - 3) / 2];
    }
}

Por supuesto, debe especificar la definición de CheckPrimality .

Answer 10

Python 3:

def is_prime(a):
    return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))

Answer 11

Según la wikipedia, el tamiz de Eratóstenes tiene complejidad O(n * (log n) * (log log n)) y requiere memoria O(n) , por lo que es un buen lugar para comenzar si no se está probando especialmente grande números.

Answer 12

Tengo una función principal que funciona hasta (2 ^ 61) -1 Aquí:

from math import sqrt
def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))

Explicación:

La función all() se puede redefinir a esto:

def all(variables):
    for element in variables:
        if not element: return False
    return True

La función all() simplemente pasa por una serie de bools / números y devuelve False si ve 0 o False .

La función sqrt() simplemente está haciendo la raíz cuadrada de un número.

Por ejemplo:

>>> from math import sqrt
>>> sqrt(9)
>>> 3
>>> sqrt(100)
>>> 10

La parte num % x devuelve el resto de num / x.

Finalmente, range(2, int(sqrt(num))) significa que creará una lista que comienza en 2 y termina en int(sqrt(num)+1)

Para obtener más información sobre el alcance, ¡eche un vistazo a este website !

La parte num > 1 solo está comprobando si la variable num es mayor que 1, porque 1 y 0 no se consideran números primos.

Espero que esto haya ayudado :)

Answer 13

En Python 3:

def is_prime(a):
if a < 2:
    return False
elif a!=2 and a % 2 == 0:
    return False
else:
    return all (a % i for i in range(3, int(a**0.5)+1) )

Explicación: Un número primo es un número solo divisible por sí mismo y 1. Ej .: 2,3,5,7 ...

1) si a <2: si "a" es menor que 2, no es un primo.

2) elif a! = 2 y a% 2 == 0: si "a" es divisible por 2, entonces definitivamente no es un primo. Pero si a = 2 no queremos evaluar eso ya que es un número primo. De ahí la condición a! = 2

3) devuelve todo (a% i para i en rango (3, int (a 0.5) +1)): ** Primero mira lo que hace all () comando en python. Comenzando desde 3, dividimos "a" hasta su raíz cuadrada (a ** 0.5). Si "a" es divisible, la salida será False. ¿Por qué raíz cuadrada? Digamos a = 16. La raíz cuadrada de 16 = 4. No es necesario evaluar hasta el 15. Solo necesitamos verificar hasta 4 para decir que no es un número primo.

Extra: un bucle para encontrar todo el número primo dentro de un rango.

for i in range(1,100):
if is_prime(i):
    print("{} is a prime number".format(i) )

Answer 14

bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}
this is just c++ implementation of above  AKS algorithm

https://en.wikipedia.org/wiki/AKS_primality_test

Answer 15

myInp=int(input("Enter a number: "))
if myInp==1:
    print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
    for i in range(2,myInp//2+1):
        if myInp%i==0:
            print("The Number {} is not a prime no".format(myInp))
            print("Because",i,"times",myInp//i,"is",myInp)
            break
    else:
        print("The Number {} is a prime no".format(myInp))
else:
    print("Alas the no {} is a not a prime no".format(myInp))

Answer 16

public static boolean isPrime(int number) {
 if(number < 2)
   return false;
 else if(number == 2 || number == 3)
        return true;
      else {
        for(int i=2;i<=number/2;i++)
           if(number%i == 0)
             return false;
           else if(i==number/2)
                return true;
      }
    return false;
}