C++ numero Primo compito dal libro

Question

io sono un principiante C++;) quanto è buono il codice qui sotto, come un modo di trovare tutti i numeri primi tra 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

L'unica risposta a tutto il testo che abbiamo pubblicato qui è: Divisione prova! Se qualcuno ha detto basi matematiche che questo compito si è basata su, ci piacerebbe risparmiare un sacco di tempo;)

Answer 2

Ti fermi quando j = io. Una prima ottimizzazione semplice è quella di fermarsi quando j = sqrt (i) (poiché non ci possono essere fattori di un numero maggiore della sua radice quadrata).

Un'implementazione molto più veloce è per esempio il sieve of eratosthenes.

Edit: il codice sembra un po 'misterioso, ecco Funziona così:

La condizione di terminazione su quello interno per è i/j, equivalente a j<i (che è molto più chiara), da quando finalmente j==i, avremo i/j==0 e il per si romperà.

Il prossimo controllo if(j>(i/j)) è davvero brutto. Fondamentalmente controlla solo se il ciclo ha colpito la condizione finale del for (quindi abbiamo un primo) o se raggiungiamo l'interruzione esplicita (nessun primo). Se raggiungiamo la fine, allora j==i+1 (pensaci su) =>i/j==0 => è un numero primo. Se colpiamo una pausa, significa j è un fattore di i, ma non una qualsiasi fattore, il più piccolo di fatto (visto che l'uscita al primo j che divide i)! Poiché j è il fattore più piccolo, l'altro fattore (o prodotto di fattori rimanenti, in i/j) dovrà essere maggiore o uguale a j, quindi il test. Se j<=i/j, facciamo una pausa e j è il più piccolo fattore di i.

Ecco qualche codice illeggibile!

Answer 3

non molto buona. A mio modesto parere, l'indentazione e la spaziatura sono orribili (senza offesa). Per ripulirlo un po ':

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"; 
    } 
} 

Questo rivela un bug: le if (j > i/j) ... ha bisogno di essere al di fuori del ciclo interno per questo al lavoro. Inoltre, penso che la condizione i/j sia più confusa (per non dire più lenta) del semplice j < i (o anche nulla, perché una volta j raggiunge i, i % j sarà 0). Dopo queste modifiche, abbiamo:

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"; 
} 

Questo funziona. Tuttavia, lo j > i/j mi confonde. Non riesco nemmeno a capire perché funzioni (suppongo che potrei capirlo se ho passato un po 'di tempo looking like this guy). Vorrei scrivere if (j == i) invece.

Ciò che avete implementato qui è chiamato trial division. Un algoritmo migliore è il setaccio di Eratostene, come pubblicato in un'altra risposta. Un paio di cose da verificare se si implementa un setaccio di Eratostene:

1. Dovrebbe funzionare.
2. Non deve utilizzare la divisione o il modulo. Non che questi siano "cattivi" (concessi, tendono ad essere un ordine di grandezza più lento di addizione, sottrazione, negazione, ecc.), Ma non sono necessari e, se sono presenti, probabilmente significa che l'implementazione non è è davvero così efficiente
3. Dovrebbe essere in grado di calcolare i numeri primi meno di 10.000.000 in circa un secondo (a seconda dell'hardware, del compilatore, ecc.).

Answer 4

Prima di tutto, il codice è sia breve che corretto, il che è molto buono per principianti. ;-)

Questo è quello che vorrei fare per migliorare il codice:

1) Definire le variabili all'interno dei cicli, in modo da non confondersi con qualcos'altro. Vorrei anche rendere il limite un parametro o una costante.

#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) Vorrei utilizzare il Sieve of Eratosthenes, come Joey Adams e Mau hanno suggerito. Nota come non devo scrivere il limite due volte, quindi i due usi saranno sempre identici.

#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; 
    } 

I limiti sono anche degni di nota. i*i<MAX è molto più veloce di j > i/j e inoltre non è necessario contrassegnare alcun numero < i * i, perché saranno già stati contrassegnati, se sono compositi. La cosa più importante è la time complexity però.

3) Se si desidera veramente rendere questo algoritmo veloce, è necessario memorizzarlo nella cache. L'idea è di trovare prima tutti i numeri primi < sqrt (MAX) e quindi usarli per trovare il resto dei numeri primi . Quindi è possibile utilizzare lo stesso blocco di memoria per trovare tutti i numeri primi da 1024-2047, ad esempio e quindi 2048-3071. Ciò significa che tutto sarà conservato nella cache L1. Una volta ho misurato un'accelerazione di ~ 12 volte usando questa ottimizzazione sul setaccio di Eratostene.

È anche possibile ridurre l'utilizzo dello spazio a metà non memorizzando i numeri pari, il che significa che non è necessario eseguire i calcoli per iniziare a lavorare su un nuovo blocco più spesso.

Se sei un principiante, dovresti probabilmente dimenticarti della cache per il 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; 
} 

Questo è il codice funziona. Ho incluso anche molte delle ottimizzazioni menzionate dai precedenti poster. Se ci sono altre ottimizzazioni che possono essere fatte, sarebbe informativo sapere.

Answer 6

Questa funzione è più efficiente per vedere se un numero è 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; 
}