saber - numeros primos c# ciclo for
C-determina si un número es primo (10)
Estoy tratando de encontrar un método que tome un número entero y devuelva un booleano para decir si el número es primo o no y no sé mucho C; ¿alguien se preocuparía de darme algunos consejos?
Básicamente, haría esto en C # así:
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}
- Construya una tabla de primos pequeños y verifique si dividen su número de entrada.
- Si el número sobrevivió a 1, pruebe las pruebas de pseudo primalidad aumentando la base. Ver la prueba de primalidad de Miller-Rabin, por ejemplo.
- Si su número sobrevivió a 2, puede concluir que es excelente si está por debajo de algunos límites bien conocidos. De lo contrario, tu respuesta solo será "probablemente primera". Encontrarás algunos valores para estos límites en la página wiki.
¡Stephen Canon respondió muy bien!
Pero
- El algoritmo puede mejorarse aún más al observar que todos los números primos tienen la forma 6k ± 1, con la excepción de 2 y 3.
- Esto se debe a que todos los enteros se pueden expresar como (6k + i) para un entero ky para i = -1, 0, 1, 2, 3 o 4; 2 divisiones (6k + 0), (6k + 2), (6k + 4); y 3 divide (6k + 3).
- Entonces, un método más eficiente es probar si n es divisible por 2 o 3, luego verificar todos los números de la forma 6k ± 1 ≤ √n.
Esto es 3 veces más rápido que probar todo m hasta √n.
int IsPrime(unsigned int number) { if (number <= 3 && number > 1) return 1; // as 2 and 3 are prime else if (number%2==0 || number%3==0) return 0; // check if number is divisible by 2 or 3 else { unsigned int i; for (i=5; i*i<=number; i+=6) { if (number % i == 0 || number%(i + 2) == 0) return 0; } return 1; } }
Comprueba el módulo de cada entero desde 2 hasta la raíz del número que estás comprobando.
Si el módulo es igual a cero, entonces no es primo.
pseudo código:
bool IsPrime(int target)
{
for (i = 2; i <= root(target); i++)
{
if ((target mod i) == 0)
{
return false;
}
}
return true;
}
Después de leer esta pregunta, me intrigó el hecho de que algunas respuestas ofrecieran optimización ejecutando un ciclo con múltiplos de 2 * 3 = 6.
Entonces creo una nueva función con la misma idea, pero con múltiplos de 2 * 3 * 5 = 30.
int check235(unsigned long n)
{
unsigned long sq, i;
if(n<=3||n==5)
return n>1;
if(n%2==0 || n%3==0 || n%5==0)
return 0;
if(n<=30)
return checkprime(n); /* use another simplified function */
sq=ceil(sqrt(n));
for(i=7; i<=sq; i+=30)
if (n%i==0 || n%(i+4)==0 || n%(i+6)==0 || n%(i+10)==0 || n%(i+12)==0
|| n%(i+16)==0 || n%(i+22)==0 || n%(i+24)==0)
return 0;
return 1;
}
Al ejecutar ambas funciones y verificar los tiempos, podría afirmar que esta función es realmente más rápida. Veamos 2 pruebas con 2 primos diferentes:
$ time ./testprimebool.x 18446744069414584321 0
f(2,3)
Yes, its prime.
real 0m14.090s
user 0m14.096s
sys 0m0.000s
$ time ./testprimebool.x 18446744069414584321 1
f(2,3,5)
Yes, its prime.
real 0m9.961s
user 0m9.964s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 0
f(2,3)
Yes, its prime.
real 0m13.990s
user 0m13.996s
sys 0m0.004s
$ time ./testprimebool.x 18446744065119617029 1
f(2,3,5)
Yes, its prime.
real 0m10.077s
user 0m10.068s
sys 0m0.004s
Entonces pensé, ¿alguien ganaría demasiado si se generaliza? Se me ocurrió una función que hará un asedio primero para limpiar una lista dada de primos primordiales, y luego usar esta lista para calcular la más grande.
int checkn(unsigned long n, unsigned long *p, unsigned long t)
{
unsigned long sq, i, j, qt=1, rt=0;
unsigned long *q, *r;
if(n<2)
return 0;
for(i=0; i<t; i++)
{
if(n%p[i]==0)
return 0;
qt*=p[i];
}
qt--;
if(n<=qt)
return checkprime(n); /* use another simplified function */
if((q=calloc(qt, sizeof(unsigned long)))==NULL)
{
perror("q=calloc()");
exit(1);
}
for(i=0; i<t; i++)
for(j=p[i]-2; j<qt; j+=p[i])
q[j]=1;
for(j=0; j<qt; j++)
if(q[j])
rt++;
rt=qt-rt;
if((r=malloc(sizeof(unsigned long)*rt))==NULL)
{
perror("r=malloc()");
exit(1);
}
i=0;
for(j=0; j<qt; j++)
if(!q[j])
r[i++]=j+1;
free(q);
sq=ceil(sqrt(n));
for(i=1; i<=sq; i+=qt+1)
{
if(i!=1 && n%i==0)
return 0;
for(j=0; j<rt; j++)
if(n%(i+r[j])==0)
return 0;
}
return 1;
}
Supongo que no optimicé el código, pero es justo. Ahora, las pruebas. Debido a la cantidad de memoria dinámica, esperaba que la lista 2 3 5 fuera un poco más lenta que la 2 3 5 codificada. Pero estuvo bien, como puedes ver abajo. Después de eso, el tiempo se hizo más y más pequeño, culminando la mejor lista para ser:
2 3 5 7 11 13 17 19
Con 8.6 segundos. Entonces, si alguien creara un programa codificado que haga uso de tal técnica, sugeriría usar la lista 2 3 y 5, porque la ganancia no es tan grande. Pero también, si está dispuesto a codificar, esta lista está bien. El problema es que no puede indicar todos los casos sin un bucle, o su código sería muy grande (habría 1658879 ORs , eso es || en el respectivo interno if ). La siguiente lista:
2 3 5 7 11 13 17 19 23
el tiempo comenzó a hacerse más grande, con 13 segundos. Aquí toda la prueba:
$ time ./testprimebool.x 18446744065119617029 2 3 5
f(2,3,5)
Yes, its prime.
real 0m12.668s
user 0m12.680s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7
f(2,3,5,7)
Yes, its prime.
real 0m10.889s
user 0m10.900s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11
f(2,3,5,7,11)
Yes, its prime.
real 0m10.021s
user 0m10.028s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13
f(2,3,5,7,11,13)
Yes, its prime.
real 0m9.351s
user 0m9.356s
sys 0m0.004s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17
f(2,3,5,7,11,13,17)
Yes, its prime.
real 0m8.802s
user 0m8.800s
sys 0m0.008s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19
f(2,3,5,7,11,13,17,19)
Yes, its prime.
real 0m8.614s
user 0m8.564s
sys 0m0.052s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23
f(2,3,5,7,11,13,17,19,23)
Yes, its prime.
real 0m13.013s
user 0m12.520s
sys 0m0.504s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23 29
f(2,3,5,7,11,13,17,19,23,29)
q=calloc(): Cannot allocate memory
PD. No liberé (r) intencionalmente, dando esta tarea al sistema operativo, ya que la memoria se liberaría tan pronto como el programa saliera, para ganar algo de tiempo. Pero sería conveniente liberarlo si tiene la intención de seguir ejecutando su código después del cálculo.
PRIMA
int check2357(unsigned long n)
{
unsigned long sq, i;
if(n<=3||n==5||n==7)
return n>1;
if(n%2==0 || n%3==0 || n%5==0 || n%7==0)
return 0;
if(n<=210)
return checkprime(n); /* use another simplified function */
sq=ceil(sqrt(n));
for(i=11; i<=sq; i+=210)
{
if(n%i==0 || n%(i+2)==0 || n%(i+6)==0 || n%(i+8)==0 || n%(i+12)==0 ||
n%(i+18)==0 || n%(i+20)==0 || n%(i+26)==0 || n%(i+30)==0 || n%(i+32)==0 ||
n%(i+36)==0 || n%(i+42)==0 || n%(i+48)==0 || n%(i+50)==0 || n%(i+56)==0 ||
n%(i+60)==0 || n%(i+62)==0 || n%(i+68)==0 || n%(i+72)==0 || n%(i+78)==0 ||
n%(i+86)==0 || n%(i+90)==0 || n%(i+92)==0 || n%(i+96)==0 || n%(i+98)==0 ||
n%(i+102)==0 || n%(i+110)==0 || n%(i+116)==0 || n%(i+120)==0 || n%(i+126)==0 ||
n%(i+128)==0 || n%(i+132)==0 || n%(i+138)==0 || n%(i+140)==0 || n%(i+146)==0 ||
n%(i+152)==0 || n%(i+156)==0 || n%(i+158)==0 || n%(i+162)==0 || n%(i+168)==0 ||
n%(i+170)==0 || n%(i+176)==0 || n%(i+180)==0 || n%(i+182)==0 || n%(i+186)==0 ||
n%(i+188)==0 || n%(i+198)==0)
return 0;
}
return 1;
}
Hora:
$ time ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real 0m9.123s
user 0m9.132s
sys 0m0.000s
Me sorprende que nadie haya mencionado esto.
Usa el tamiz de Eratóstenes
Detalles:
- Básicamente, los números no primos son divisibles por otro número además de 1 y ellos mismos
- Por lo tanto: un número no principal será un producto de números primos.
El tamiz de Eratóstenes encuentra un número primo y lo almacena. Cuando se verifica que un número nuevo es primo, todos los números primos anteriores se comparan con la lista principal conocida.
Razones:
- Este algoritmo / problema se conoce como " embarazosamente paralelo "
- Crea una colección de números primos
- Es un ejemplo de un problema de programación dinámico
- ¡Es rápido!
OK, así que olvídate de C. Supongamos que te doy un número y te pido que determines si es el primero. ¿Cómo lo haces? Escriba los pasos con claridad, luego preocúpese por traducirlos en código.
Una vez que haya determinado el algoritmo, será mucho más fácil para usted descubrir cómo escribir un programa y para que otros lo ayuden con él.
editar: Aquí está el código de C # que publicó:
static bool IsPrime(int number) {
for (int i = 2; i < number; i++) {
if (number % i == 0 && i != number) return false;
}
return true;
}
Esta es una C casi tan válida como es; no hay ningún tipo de bool en C, y no es true o false , por lo que debe modificarlo un poco (edit: Kristopher Johnson señala correctamente que C99 agregó el encabezado stdbool.h). Como algunas personas no tienen acceso a un entorno C99 (¡pero debe usar uno!), Hagamos un cambio muy pequeño:
int IsPrime(int number) {
int i;
for (i=2; i<number; i++) {
if (number % i == 0 && i != number) return 0;
}
return 1;
}
Este es un programa C perfectamente válido que hace lo que quiere. Podemos mejorarlo un poco sin demasiado esfuerzo. En primer lugar, tenga en cuenta que siempre es menor que el number , por lo que la comprobación de que i != number siempre tiene éxito; podemos deshacernos de eso.
Además, en realidad no necesitas probar los divisores hasta el number - 1 ; puede dejar de verificar cuando llegue a sqrt (número). Dado que sqrt es una operación de coma flotante y que aporta una gran cantidad de sutilezas, en realidad no calcularemos sqrt(number) . En cambio, podemos verificar que i*i <= number :
int IsPrime(int number) {
int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
Una última cosa, sin embargo; ¡hubo un pequeño error en tu algoritmo original! Si el number es negativo, o cero, o uno, esta función afirmará que el número es primo. Es probable que desee manejarlo correctamente, y es posible que desee que el number no esté firmado, ya que es más probable que solo le interesen los valores positivos:
int IsPrime(unsigned int number) {
if (number <= 1) return 0; // zero and one are not prime
unsigned int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
Definitivamente, esta no es la manera más rápida de verificar si un número es primo, pero funciona, y es bastante sencillo. ¡Apenas tuvimos que modificar tu código!
Solo agregaría que ningún número par (barra 2) puede ser un número primo. Esto da como resultado otra condición antes del ciclo for. Entonces, el código final debe verse así:
int IsPrime(unsigned int number) {
if (number <= 1) return 0; // zero and one are not prime
if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2)
unsigned int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
Utilizando Sieve of Eratosthenes, el cálculo es bastante más rápido que el algoritmo de números primos "conocidos".
Al usar pseudocódigo en su wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), puedo tener la solución en C #.
public bool IsPrimeNumber(int val) {
// Using Sieve of Eratosthenes.
if (val < 2)
{
return false;
}
// Reserve place for val + 1 and set with true.
var mark = new bool[val + 1];
for(var i = 2; i <= val; i++)
{
mark[i] = true;
}
// Iterate from 2 ... sqrt(val).
for (var i = 2; i <= Math.Sqrt(val); i++)
{
if (mark[i])
{
// Cross out every i-th number in the places after i (all the multiples of i).
for (var j = (i * i); j <= val; j += i)
{
mark[j] = false;
}
}
}
return mark[val];
}
IsPrimeNumber (1000000000) tarda 21s 758ms.
NOTA : El valor puede variar según las especificaciones del hardware.
este programa es muy eficiente para verificar un solo número para la verificación de primalidad.
bool check(int n){
if (n <= 3) {
return n > 1;
}
if (n % 2 == 0 || n % 3 == 0) {
return false;
}
int sq=sqrt(n); //include math.h or use i*i<n in for loop
for (int i = 5; i<=sq; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
int is_prime(int val)
{
int div,square;
if (val==2) return TRUE; /* 2 is prime */
if ((val&1)==0) return FALSE; /* any other even number is not */
div=3;
square=9; /* 3*3 */
while (square<val)
{
if (val % div == 0) return FALSE; /* evenly divisible */
div+=2;
square=div*div;
}
if (square==val) return FALSE;
return TRUE;
}
El manejo de 2 y números pares se mantienen fuera del bucle principal, que solo maneja números impares divididos por números impares. Esto se debe a que un número impar, un módulo y un número par darán siempre una respuesta distinta de cero que hace que esas pruebas sean redundantes. O, para decirlo de otra manera, un número impar puede ser divisible por igual por otro número impar pero nunca por un número par (E * E => E, E * O => E, O * E => E y O * O => O).
Una división / módulo es realmente costosa en la arquitectura x86 aunque lo costoso varía (ver http://gmplib.org/~tege/x86-timing.pdf ). Las multiplicaciones, por otro lado, son bastante baratas.