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:
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:
Stephen Canon ha risposto molto bene!
Ma
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; } }
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.