C++ tarea número primo del libro

Question

yo soy un principiante C++;) ¿Qué tan bueno es el código abajo como una manera de encontrar todos los números primos entre 2-1000:

int i, j; 

for (i=2; i<1000; i++) { 
    for (j=2; j<=(i/j); j++) { 
    if (! (i%j)) 
     break; 
    if (j > (i/j)) 
     cout << i << " is prime\n"; 
    } 
} 

Answer 1

La respuesta simple a todo el montón de texto que publicamos aquí es: División de prueba! Si alguien mencionó base matemática que esta tarea se basa en, ahorraríamos un montón de tiempo;)

Answer 2

te detenga cuando j = yo. Una primera optimización simple es detener cuando j = sqrt (i) (ya que no puede haber factores de un número mayor que su raíz cuadrada).

Una implementación mucho más rápida es, por ejemplo, sieve of eratosthenes.

Editar: el código es algo misterioso, por lo que aquí es cómo funciona:

La condición de terminación en el interior para es i/j, equivalente a j<i (que es mucho más claro), ya que al fin tenemos j==i, tendremos i/j==0 y el for se romperá.

El siguiente cheque if(j>(i/j)) es realmente desagradable. Básicamente, solo verifica si el bucle golpea la condición de fin de for (por lo tanto, tenemos un primo) o si alcanzamos la ruptura explícita (sin prima). Si pulsamos el para, entonces j==i+1 (piénselo) =>i/j==0 => es un número primo. Si alcanzamos un salto, significa j es un factor de i, pero no cualquier factor, el más pequeño de hecho (¡ya que salimos en el primer j que divide i)! Dado que j es el factor más pequeño, el otro factor (o producto de factores restantes, dado por i/j) será mayor o igual a j, de ahí la prueba. Si j<=i/j, llegamos a un corte y j es el factor más pequeño de i.

¡Es un código ilegible!

Answer 3

No muy bueno. En mi humilde opinión, la sangría y el espaciado es horrible (sin ofender). Para limpiarlo alguna:

int i, j; 

for (i=2; i<1000; i++) { 
    for (j=2; i/j; j++) { 
     if (!(i % j)) 
      break; 
     if (j > i/j) 
      cout << i << " is prime\n"; 
    } 
} 

Esto revela un error: los if (j > i/j) ... tiene que estar en el exterior del bucle interno para que esto funcione. Además, creo que la condición i/j es más confusa (por no mencionar más lenta) que simplemente decir j < i (o incluso nada, porque una vez que j llegue a i, i % j será 0). Después de estos cambios, tenemos:

int i, j; 

for (i=2; i<1000; i++) { 
    for (j=2; j < i; j++) { 
     if (!(i % j)) 
      break; 
    } 
    if (j > i/j) 
     cout << i << " is prime\n"; 
} 

Esto funciona. Sin embargo, el j > i/j me confunde. Ni siquiera puedo entender por qué funciona (supongo que podría resolverlo si pasé un tiempo looking like this guy). Yo escribiría if (j == i) en su lugar.

Lo que ha implementado aquí se llama trial division. Un mejor algoritmo es el Tamiz de Eratóstenes, como se publicó en otra respuesta. Un par de cosas para comprobar si implementa un Tamiz de Eratóstenes:

1. Debería funcionar.
2. No debería usar división o módulo. No es que estos sean "malos" (se les concede, tienden a ser un orden de magnitud más lento que la suma, la resta, la negación, etc.), pero no son necesarios, y si están presentes, probablemente signifique que la implementación no es necesaria. No es tan eficiente.
3. Debería poder calcular los números primos de menos de 10,000,000 en aproximadamente un segundo (dependiendo de su hardware, compilador, etc.).

Answer 4

En primer lugar, su código es corto y correcto, lo cual es muy bueno para principiantes. ;-)

Esto es lo que haría para mejorar el código:

1) Definir las variables dentro de los bucles, por lo que no se confunda con otra cosa. También haría que el límite sea un parámetro o una constante.

#define MAX 1000 
for(int i=2;i<MAX;i++){ 
    for(int j=2;j<i/j;j++){ 
     if(!(i%j)) break; 
     if(j>(i/j)) cout<<i<<" is prime\n"; 
    } 
} 

2) Me gustaría utilizar el Sieve of Eratosthenes, como Joey Adams y Mau han sugerido. Observe cómo no tengo que escribir el límite dos veces, por lo que los dos usos siempre serán idénticos.

#define MAX 1000 
bool prime[MAX]; 
memset(prime, sizeof(prime), true); 
for(int i=4;i<MAX;i+=2) prime[i] = false; 
prime[1] = false; 
cout<<2<<" is prime\n"; 
for(int i=3;i*i<MAX;i+=2) 
    if (prime[i]) { 
     cout<<i<<" is prime\n"; 
     for(int j=i*i;j<MAX;j+=i) 
      prime[j] = false; 
    } 

Los límites también son dignos de mención. i*i<MAX es mucho más rápido que j > i/j y tampoco es necesario marcar ningún número < i * i, porque ya estarán marcados, si son compuestos. Sin embargo, lo más importante es el time complexity.

3) Si realmente desea hacer que este algoritmo sea rápido, necesita caché para optimizarlo. La idea es encontrar primero todos los números primos < sqrt (MAX) y luego usarlos para encontrar el resto de los números primos . Luego puede usar el mismo bloque de memoria para encontrar todos los números primos desde 1024-2047, por ejemplo, y luego 2048-3071. Esto significa que todo se mantendrá en L1-caché. Una vez midí una aceleración de ~ 12 veces usando esta optimización en el Tamiz de Eratóstenes.

También puede reducir el uso de espacio a la mitad al no almacenar los números pares, lo que significa que no tiene que realizar los cálculos para comenzar a trabajar en un bloque nuevo tan a menudo.

Si es un principiante, probablemente debería olvidarse del caché por el momento.

Answer 5

#include <stdio.h> 
#define N 1000 

int main() 
{ 

    bool primes[N]; 
    for(int i = 0 ; i < N ; i++) primes[i] = false; 
    primes[2] = true; 

    for(int i = 3 ; i < N ; i+=2) { // Check only odd integers  
     bool isPrime = true;  
     for(int j = i/2 ; j > 2 ; j-=2) { // Check only from largest possible multiple of current number 
      if (j%2 == 0) { j = j-1; } // Check only with previous odd divisors 
      if(!primes[j]) continue;  // Check only with previous prime divisors 
      if (i % j == 0) {    
       isPrime = false; 
       break; 
      } 
     } 
     primes[i] = isPrime; 
    } 

    return 0; 
} 

Este código está trabajando. También incluí muchas de las optimizaciones mencionadas en los carteles anteriores. Si hay otras optimizaciones que se pueden hacer, sería informativo saberlo.

Answer 6

Esta función es más eficiente para ver si un número es primo.

bool isprime(const unsigned long n) 
{ 
if (n<2) return false; 
if (n<4) return true; 
if (n%2==0) return false; 
if (n%3==0) return false; 
unsigned long r = (unsigned long) sqrt(n); 
r++; 
for(unsigned long c=6; c<=r; c+=6) 
{ 
    if (n%(c-1)==0) return false; 
    if (n%(c+1)==0) return false; 
}