¿Es usted primer número

Question

? He estado interesado en el problema de encontrar un mejor reconocedor de números primos durante años. Me doy cuenta de que esta es una gran área de investigación académica y estudio; mi interés en esto es solo por diversión. Aquí estaba mi primer intento de una posible solución, en C (abajo).

Mi pregunta es, ¿pueden sugerir una mejora (sin citar alguna otra referencia en la red, estoy buscando el código C real)? Lo que intento obtener de esto es una mejor comprensión de la determinación de la complejidad del rendimiento de una solución como esta.

¿Estoy en lo cierto al concluir que la complejidad de esta solución es O (n^2)?

#include <stdio.h> 
#include <math.h> 

/* isprime               */ 
/* Test if each number in the list from stdin is prime.    */ 
/* Output will only print the prime numbers in the list.    */ 

int main(int argc, char* argv[]) { 

    int returnValue = 0; 
    int i; 
    int ceiling; 
    int input = 0; 
    int factorFound = 0; 

    while (scanf("%d", &input) != EOF) { 

     ceiling = (int)sqrt(input); 
     if (input == 1) { 
      factorFound = 1; 
     } 

     for (i = 2; i <= ceiling; i++) { 
      if (input % i == 0) { 
       factorFound = 1; 
      } 
     } 

     if (factorFound == 0) { 
      printf("%d\n", input); 
     } 

     factorFound = 0;  
    } 

    return returnValue; 
} 

Answer 1

for (i = 2; i <= ceiling; i++) { 
     if (input % i == 0) { 
      factorFound = 1; 
      break; 
     } 
    } 

Ésta es la primera mejora de hacer y aún así mantenerse dentro de los límites de la "misma" algoritmo. No requiere ninguna matemática para ver este.

Más allá de eso, una vez que ve que input no es divisible por 2, no hay necesidad de comprobar 4, 6, 8, etc. Si cualquier número par dividido en input, seguramente 2 tendría porque divide todo Números pares.

Si quiere salir un poco del algoritmo, puede usar un bucle como el que Sheldon L. Cooper proporciona en su respuesta. (Esto es simplemente más fácil que tener que corregir mi código de los comentarios, aunque sus esfuerzos son muy apreciados)

esto aprovecha el hecho de que cada primo diferente de 2 y 3 tiene el formato n*6 + 1 o n*6 - 1 para un entero positivo n. Para ver esto, sólo tenga en cuenta que si m = n*6 + 2 o m = n*6 + 4, entonces n es divisible por 2. Si m = n*6 + 3 entonces es divisible por 3.

De hecho, podemos ir más lejos. Si p1, p2, .., pk son los primeros números primos k, todos los enteros que coinciden con su producto marcan 'ranuras' en las que deben coincidir todos los primos restantes.

para ver esto, simplemente deje que k# sea el producto de todas las primos hasta pk. luego, si gcd(k#, m) = g, g divide n*k# + m y esta suma es trivialmente compuesta si g != 1. así que si quieres a repetir en términos de 5# = 30, a continuación, sus números primos entre sí son 1, 7, 11, 13, 17, 19, 23 y 29.

---

técnicamente, no resultó mi último reclamo. No es mucho más difícil

si g = gcd(k#, m), entonces para cualquier número entero, n, g divide n*k# + m porque divide k# por lo que también debe dividir n*k#. Pero también divide m, por lo que debe dividir la suma. Arriba, solo lo probé para n = 1. mi error.

---

Además, debo señalar que nada de esto está cambiando la complejidad fundamental del algoritmo, que seguirá siendo O (n^1/2). Todo lo que hace es drásticamente reduciendo el coeficiente que se usa para calcular los tiempos de ejecución reales esperados.

Answer 2

No hay forma de mejorar el algoritmo. Puede haber pequeñas formas de mejorar su código, pero no la velocidad base (y la complejidad) del algoritmo.

EDITAR: Por supuesto, ya que no necesita conocer todos los factores, solo si es un número primo o no. Gran lugar.

Answer 3

A simple mejora sería cambiar el bucle de romper cuando encuentra un factor:

for (i = 2; i <= ceiling && !factorFound; i++) { 
     if (input % i == 0) { 
      factorFound = 1; 

Otra posibilidad sería la de incrementar el contador por 2 (después de comprobar 2 en sí).

Answer 4

Los números pares (excepto 2) no pueden ser números primos. Entonces, una vez que sabemos que el número no es par, podemos simplemente verificar si los números impares son sus factores.

for (i = 3; i <= ceiling; i += 2) { 
     if (input % i == 0) { 
      factorFound = 1; 
      break; 
     } 
    } 

Answer 5

Su código no solamente tiene complejidad O (sqrt (n) lg (n)). Si supone que las operaciones matemáticas básicas son O (1) (verdaderas hasta que empiece a usar bignums), entonces es solo O (sqrt (n)).

Tenga en cuenta que la prueba de primalidad se puede realizar en un tiempo más rápido que-O (sqrt (n) lg (n)). This site tiene una serie de implementaciones del AKS primality test, que se ha demostrado que funciona en O ((log n)^12) tiempo.

También existen algunas pruebas muy rápidas, aunque rápidas, a veces dan un resultado incorrecto. Por ejemplo, el Fermat primality test:

dado un número p queremos probar de primalidad, elige un número aleatorio a, y probar si a^(p-1) mod p = 1. Si es falso, p definitivamente no es primo. Si es verdadero, p es probablemente prime. Al repetir la prueba con diferentes valores aleatorios de a, se puede reducir la probabilidad de un falso positivo.

Tenga en cuenta que esta prueba específica tiene algunas fallas - vea la página de Wikipedia para más detalles y otras pruebas de primalidad probabilística que puede usar.

Si desea seguir con el enfoque actual, hay una serie de mejoras menores que aún se pueden realizar, como han señalado otros, después de 2, todos los primos adicionales son impares, por lo que puede omitir dos factores potenciales en un tiempo en el circuito. También puede salir de inmediato cuando encuentre un factor. Sin embargo, esto no cambia el comportamiento asintótico del peor de los casos de su algoritmo, que permanece en O (sqrt (n) lg (n)) - simplemente cambia el mejor de los casos (a O (lg (n))), y reduce el factor constante en aproximadamente la mitad.

Answer 6

puede sugerir una mejora

Aquí tienes ... no para el algoritmo, pero para el programa en sí :)

• Si no va a utilizar argc y argv, deshágase de ellos
• ¿Qué sucede si ingreso "fortytwo"?Comparar scanf() == 1, no != EOF
• No hay necesidad de convertir el valor de sqrt()
• returnValue no es necesario, puede volver una constante: return 0;
• En lugar de tener toda la funcionalidad dentro de la función main(), separada su programa en todas las funciones que pueda imaginar.

Answer 7

Puede hacer pequeños cortes en su algoritmo sin agregar demasiada complejidad de código. Por ejemplo, puede omitir los números pares en su verificación y detener la búsqueda tan pronto como encuentre un factor.

if (input < 2 || (input != 2 && input % 2 == 0)) 
    factorFound = 1; 

if (input > 3) 
    for (i = 3; i <= ceiling && !factorFound; i += 2) 
    if (input % i == 0) 
     factorFound = 1; 

En cuanto a la complejidad, si n es su número de entrada, no sería la complejidad O (sqrt (n)), como lo están haciendo más o menos como máximo sqrt (n) las divisiones y las comparaciones?

Answer 8

La complejidad de tiempo de su programa es O(n*m^0.5). Con n el número de primos en la entrada. Y m el tamaño del primo más grande en la entrada, o MAX_INT si lo prefiere. Así que la complejidad también se puede escribir como O(n) con n el número de primos para verificar.

Con Big-O, n es (por lo general) el tamaño de la entrada, en su caso sería el número de primos para verificar. Si hago esta lista dos veces más grande (por ejemplo, duplicarla), tomaría (+ -) exactamente el doble de tiempo, por lo tanto, O(n).

Answer 9

La complejidad del tiempo para cada prueba de primalidad en su algoritmo es O(sqrt(n)).

Siempre puede utilizar el hecho de que todos los números primos excepto 2 y 3 tienen la forma: 6*k+1 o 6*k-1. Por ejemplo:

int is_prime(int n) { 
    if (n <= 1) return 0; 
    if (n == 2 || n == 3) return 1; 
    if (n % 2 == 0 || n % 3 == 0) return 0; 
    int k; 
    for (k = 6; (k-1)*(k-1) <= n; k += 6) { 
    if (n % (k-1) == 0 || n % (k+1) == 0) return 0; 
    } 
    return 1; 
} 

Esta optimización no mejora la complejidad asintótica.

EDITAR

Teniendo en cuenta que en su código que está probando los números en repetidas ocasiones, es posible que desee comprobar la validez de calcular una lista de números primos. Solo hay 4792 números primos inferiores o iguales a la raíz cuadrada de INT_MAX (suponiendo entradas de 32 bits).

Por otra parte, si los números de entrada son relativamente pequeñas puede intentar calcular un sieve.

Aquí hay una combinación de ambas ideas:

#define UPPER_BOUND 46340 /* floor(sqrt(INT_MAX)) */ 
#define PRIME_COUNT 4792 /* number of primes <= UPPER_BOUND */ 

int prime[PRIME_COUNT]; 
int is_prime_aux[UPPER_BOUND]; 

void fill_primes() { 
    int p, m, c = 0; 
    for (p = 2; p < UPPER_BOUND; p++) 
    is_prime_aux[p] = 1; 
    for (p = 2; p < UPPER_BOUND; p++) { 
    if (is_prime_aux[p]) { 
     prime[c++] = p; 
     for (m = p*p; m < UPPER_BOUND; m += p) 
     is_prime_aux[m] = 0; 
    } 
    } 
} 

int is_prime(int n) { 
    if (n <= 1) return 0; 
    if (n < UPPER_BOUND) return is_prime_aux[n]; 
    int i; 
    for (i = 0; i < PRIME_COUNT && prime[i]*prime[i] <= n; i++) 
    if (n % prime[i] == 0) 
     return 0; 
    return 1; 
} 

llamada fill_primes al comienzo de su programa, antes de comenzar a procesar consultas. Funciona bastante rápido.

Answer 10

Aquí es mi algoritmo, Complejidad permanece O(n^0.5) pero logró sacar algunas operaciones costosas en el código ...

parte más lenta del algoritmo es la operación modulus, me las he arreglado para eliminar o hacer sqrti * i <= n

De esta manera puedo guardar ciclos preciosos ... su base en el hecho de que sum of odd numbers is always a perfect square.

Puesto que somos iterando sobre odd numbers de todos modos, ¿por qué no explotarlo? :)

int isPrime(int n) 
{ 
    int squares = 1; 
    int odd = 3; 

    if(((n & 1) == 0) || (n < 9)) return (n == 2) || ((n > 1) && (n & 1)); 
    else 
    { 
     for(;squares <= n; odd += 2) 
     { 
      if(n % odd == 0) 
       return 0; 
      squares+=odd; 
     } 
     return 1; 
    } 
} 

Answer 11

#include <stdio.h> 
#include <math.h> 

int IsPrime (int n) { 
    int i, sqrtN; 
    if (n < 2) { return 0; } /* 1, 0, and negatives are nonprime */ 
    if (n == 2) { return 2; } 
    if ((n % 2) == 0) { return 0; } /* Check for even numbers */ 
    sqrtN = sqrt((double)n)+1; /* We don't need to search all the way up to n */ 
    for (i = 3; i < sqrtN; i += 2) { 
    if (n % i == 0) { return 0; } /* Stop, because we found a factor! */ 
    } 
    return n; 
} 

int main() 
{ 
    int n; 
    printf("Enter a positive integer: "); 
    scanf("%d",&n); 
    if(IsPrime(n)) 
    printf("%d is a prime number.",n); 
    else 
    printf("%d is not a prime number.",n); 
    return 0; 
}