C – ¿Cómo probar fácilmente si es un número primo?

Posibles duplicados:
C – determina si un número es primo

¿Hay alguna forma de probar fácilmente en C si un número seleccionado es primo o no?

La forma más fácil es escribir un bucle, como:

int is_prime(int num) { if (num <= 1) return 0; if (num % 2 == 0 && num > 2) return 0; for(int i = 3; i < num / 2; i+= 2) { if (num % i == 0) return 0; } return 1; } 

Luego puede optimizarlo, iterando a floor(sqrt(num)) .

Podrías intentar usar el Tamiz de Eratóstenes:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Fácilmente encontrarás varias implementaciones de este algoritmo.

La forma más rápida es precalcular una matriz de bits (que indica prime / nonprime) de todos los enteros posibles en el rango que le interesa. Para enteros sin signo de 32 bits, eso es solo 512M, que se ajustará fácilmente en los espacios de direcciones modernos (y incluso si no fuera así, sería una búsqueda rápida de archivos).

Esto seguramente será más rápido que calcularlo a través de un tamiz cada vez.