C: determina se un numero è primo

Sto cercando di trovare un metodo che prende un numero intero e restituisce un valore booleano per dire se il numero è primo o meno e non conosco molto C; qualcuno dovrebbe darmi qualche suggerimento?

Fondamentalmente, lo farei in C # come questo:

static bool IsPrime(int number) { for (int i = 2; i < number; i++) { if (number % i == 0 && i != number) return false; } return true; } 

OK, quindi dimentica C. Supponiamo di darti un numero e chiederti di stabilire se è primo. Come si fa? Annota chiaramente i passaggi, quindi preoccupati di tradurli in codice.

Una volta determinato l’algoritmo, sarà molto più facile per te capire come scrivere un programma e per gli altri per aiutarti con esso.

modifica: ecco il codice C # che hai postato:

 static bool IsPrime(int number) { for (int i = 2; i < number; i++) { if (number % i == 0 && i != number) return false; } return true; } 

Questo è quasi C valido come è; non c'è il tipo bool in C e non è true o false , quindi è necessario modificarlo un po '(modifica: Kristopher Johnson sottolinea correttamente che C99 ha aggiunto l'intestazione stdbool.h). Dal momento che alcune persone non hanno accesso a un ambiente C99 (ma dovresti usarne uno!), Facciamo una modifica molto piccola:

 int IsPrime(int number) { int i; for (i=2; i 

Questo è un programma C perfettamente valido che fa quello che vuoi. Possiamo migliorarlo un po 'senza troppi sforzi. Innanzitutto, nota che i è sempre inferiore al number , quindi il controllo che i != number sempre esito positivo; possiamo sbarazzarcene.

Inoltre, non è necessario provare i divisori fino a number - 1 ; puoi smettere di controllare quando raggiungi sqrt (numero). Dato che sqrt è un'operazione a virgola mobile e che porta un'intera pila di sottigliezze, in realtà non calcoleremo sqrt(number) . Invece, possiamo solo controllare che i*i <= number :

 int IsPrime(int number) { int i; for (i=2; i*i<=number; i++) { if (number % i == 0) return 0; } return 1; } 

Un'ultima cosa, però; c'era un piccolo bug nell'algoritmo originale! Se il number è negativo, o zero, o uno, questa funzione asserirà che il numero è primo. Probabilmente vorresti gestirlo correttamente, e potresti voler rendere il number non firmato, dal momento che è più probabile che ti interessi solo per i valori positivi:

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

Questo sicuramente non è il modo più veloce per verificare se un numero è primo, ma funziona, ed è piuttosto semplice. Abbiamo appena dovuto modificare il tuo codice a tutti!

Sono sorpreso che nessuno ha menzionato questo.

Usa il setaccio di Eratostene

Dettagli:

  1. In pratica, i numeri non primitivi sono divisibili per un altro numero oltre a 1 e a se stessi
  2. Pertanto: un numero non primo sarà un prodotto di numeri primi.

Il setaccio di Eratostene trova un numero primo e lo immagazzina. Quando un nuovo numero viene verificato per la primità, tutti i precedenti precedenti vengono controllati rispetto all’elenco dei primari noti.

Motivi:

  1. Questo algoritmo / problema è noto come ” Embarrassingly Parallel ”
  2. Crea una collezione di numeri primi
  3. È un esempio di un problema di programmazione dynamic
  4. È veloce!

Stephen Canon ha risposto molto bene!

Ma

  • L’algoritmo può essere ulteriormente migliorato osservando che tutti i numeri primi sono di forma 6k ± 1, ad eccezione di 2 e 3.
  • Questo perché tutti gli interi possono essere espressi come (6k + i) per alcuni interi k e per i = -1, 0, 1, 2, 3 o 4; 2 divide (6k + 0), (6k + 2), (6k + 4); e 3 divide (6k + 3).
  • Quindi un metodo più efficiente è quello di verificare se n è divisibile per 2 o 3, quindi per controllare tutti i numeri di forma 6k ± 1 ≤ √n.
  • Questo è 3 volte più veloce di testare tutti fino a √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; } } 
  1. Costruisci una tabella di piccoli numeri primi e controlla se dividono il tuo numero di input.
  2. Se il numero è sopravvissuto a 1, prova i test di pseudo primalità su base crescente. Vedi ad esempio il test di primalità di Miller-Rabin .
  3. Se il tuo numero è sopravvissuto a 2, puoi concludere che è primo se è al di sotto di limiti ben noti. Altrimenti la tua risposta sarà “probabilmente primo”. Troverai alcuni valori per questi limiti nella pagina wiki.

questo programma è molto efficiente per il controllo di un singolo numero per il controllo della primalità.

 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 

Controlla il modulo di ogni intero da 2 fino alla radice del numero che stai controllando.

Se il modulo è uguale a zero, non è primo.

codice pseudo:

 bool IsPrime(int target) { for (i = 2; i <= root(target); i++) { if ((target mod i) == 0) { return false; } } return true; } 

Vorrei solo aggiungere che nessun numero pari (barra 2) può essere un numero primo. Ciò si traduce in un’altra condizione prima del ciclo. Quindi il codice finale dovrebbe assomigliare a questo:

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

Dopo aver letto questa domanda, sono rimasto affascinato dal fatto che alcune risposte offrivano un’ottimizzazione eseguendo un ciclo con multipli di 2 * 3 = 6.

Quindi creo una nuova funzione con la stessa idea, ma con multipli di 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; } 

Eseguendo entrambe le funzioni e controllando i tempi potrei affermare che questa funzione è molto più veloce. Vediamo 2 test con 2 numeri primi diversi:

 $ 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 

Quindi ho pensato che qualcuno avrebbe guadagnato troppo se generalizzato? Ho trovato una funzione che prima avrebbe fatto un assedio per pulire una data lista di numeri primi primordiali, e quindi usare questa lista per calcolare quella più 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 

Immagino di non aver ottimizzato il codice, ma è giusto. Ora, i test. Poiché così tante memorie dinamiche, mi aspettavo che la lista 2 3 5 fosse un po 'più lenta rispetto alla 2 3 5 hard-coded. Ma era ok come puoi vedere qui sotto. In seguito, il tempo è diventato sempre più piccolo, culminando con la lista migliore per essere:

2 3 5 7 11 13 17 19

Con 8,6 secondi. Quindi, se qualcuno crea un programma codificato che fa uso di tale tecnica, suggerirei di usare la lista 2 3 e 5, perché il guadagno non è così grande. Ma anche, se disposto a codificare, questa lista è ok. Il problema è che non puoi dichiarare tutti i casi senza un ciclo, o il tuo codice sarebbe molto grande (ci sarebbero 1658879 ORs , cioè || nel rispettivo interno if ). Il prossimo elenco:

2 3 5 7 11 13 17 19 23

il tempo ha iniziato a diventare più grande, con 13 secondi. Qui l'intero test:

 $ 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 

PS. Non ho liberato (r) intenzionalmente, assegnando questo compito al sistema operativo, poiché la memoria sarebbe stata liberata non appena il programma è uscito, per guadagnare un po 'di tempo. Ma sarebbe saggio liberarlo se si intende continuare a eseguire il codice dopo il calcolo.


BONUS

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

Tempo:

 $ time ./testprimebool.x 18446744065119617029 7 h(2,3,5,7) Yes, its prime. real 0m9.123s user 0m9.132s sys 0m0.000s 
 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 

La gestione di 2 e numeri pari viene mantenuta fuori dal ciclo principale che gestisce solo numeri dispari divisi per numeri dispari. Questo perché un numero dispari modulo un numero pari darà sempre una risposta diversa da zero che rende ridondanti quei test. Oppure, per dirla in altro modo, un numero dispari può essere equamente divisibile per un altro numero dispari ma mai per un numero pari (E * E => E, E * O => E, O * E => E e O * O => O).

Una divisione / modulo è davvero costosa sull'architettura x86, anche se varia il suo costo (vedi http://gmplib.org/~tege/x86-timing.pdf ). Le moltiplicazioni d'altra parte sono piuttosto economiche.

Usando il Sieve di Eratostene, il calcolo è molto più veloce rispetto all’algoritmo dei numeri primi “conosciuti”.

Usando lo pseudocodice dal suo wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), posso avere la soluzione su 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) richiede 21s 758ms.

NOTA : il valore può variare in base alle specifiche dell'hardware.