Newsgroup: it.comp.lang.c
Titolo: semi-OT:Come faccio a sapere se un numero è primo?

Ciao a tutti, ho provato a fare un programmino che contasse i numeri primi
presenti in un insieme definito dall'utente(da me limitato a
2.000.000.000)....
Il problema è che le mie conoscenze sui metodi per trovare i numeri primi si
fermano al fatto di provare a dividerli per 3, 5, 7, 11,..., 101 per vedere
se il loro modulo è uguale a 0 o no....
Ma  così verifico solo se un numero non è primo e i numeri primi che trovo
potrebbero non esserlo(anche se comunque la percentuale di numeri primi che
ho riscontrato collima abbastanza con 1/log n dati n numeri....)
Domanda: come si fa a sapere se un numero è primo senza doverlo dividere per
tutti i numeri primi minori di quel numero?
Grazie per le eventuali risposte....
Steve

 wrote in message
Len55.276623$VM3.2...@news.infostrada.it...

Basta dividerlo per tutti i numeri primi minori o equali della sua
radice quadrata.  A parte questo, non c'e` un metodo deterministico,
anche se c'e` un metodo molto interessante che funziona invece in
modo _probabilistico_.
Il "Test di Miller"...: sia n = 1 + (2**r) * m per un qualche r>=1
e m dispari.  Dato un qualsiasi b tale che gcd(b,n)==1, si dice
che "n passa il Test di Miller in base b" se e solo se:
-- o (b**m) mod n == +1 o -1, oppure
-- b**(2**k) mod n == -1 per un qualche k <= r
La cosa piu` importante e` il seguente teorema: se n e` non-primo,
esso passa il Test di Miller per AL MASSIMO (n-1)/4 basi b <= n-1;
se e` primo, esso passa il Test di Miller per ogni base siffatta.
Da cui, il Test Probabilistico per numeri primi di Rabin-Miller...:
sia n un intero positivo dispari, e, per un qualche k, b[i] con
i da 1 a k siano numeri tali che, per ciascun i,
    1 < b[i] < n-1
e
    gcd(b[i], n) == 1
Se n passa il test di Miller per ognuna di queste basi b[i], allora
la probabilita` che n sia primo e` almeno 1 - (1/4)**k.
L'implementazione non e` proprio banale, ma ne trovi un esempio
a: 
http://www.middlebury.edu/~pemerson/thesis/node10.html#rabinprogram
Piu` in generale, la tesi di P. Emerson, che puoi trovare ad
esempio a 
http://pantheon.yale.edu/~pre6/
, e` un ottimo punto
di partenza sul suo tema, "Prime Generation and Primality Testing".
La versione HTML e` a 
http://www.middlebury.edu/~pemerson/thesis/
.
Alex

 
Se trovi l'algoritmo brevettalo: e' un problema aperto e ci faresti un
sacco di soldi (forse) ;-)
--
 Ciao, Bianco.
 Reply to 
luca....@tiscalinet.it

 sacco di soldi (forse) ;-)
Guarda sono buono e credo nell'Open Source    ^____^
Eccoti un'implementazione:
#include <stdio.h>
#include <math.h>
#include <time.h>
main()
{
time_t inizio,fine;
long campo;
long verifica;
long i;
double calcoli=0;
int durata;
unsigned long perc_primi;
unsigned long perc_divisibili;
long primi=0;
long nonprimi=0;
long campo2;
/*FILE *fp;
FILE *fp2;
fp=fopen("primi.txt","w");
fp2=fopen("nonprimi.txt","w");*/
printf("\nInserire il campo di numeri: ");
scanf("%ld",&campo2);
if((campo2<5) || (campo2>
2147000000
))
{
return main();
}
campo=5;
time(&inizio);
while(campo<=campo2)
{
 for(i=2;i<=sqrt(campo);i++)
  {
   calcoli++;
   verifica=campo%i;
   if(verifica==0)
   {
    /*fprintf(fp2,"Il numero %ld é divisibile per %ld\n",campo,i);*/
    nonprimi++;
    break;
   }
  }
  if(verifica!=0)
   {
    /*fprintf(fp,"Il numero %ld é primo!\n",campo);*/
    primi++;
   }
 campo++;
}
time(&fine);
durata=difftime(fine,inizio);
perc_primi=((primi*100)/campo2);
perc_divisibili=((nonprimi*100)/campo2);
printf("\nI numeri primi sono %ld su %ld cioé il %u per
cento",primi,campo2,perc_primi);
printf("\nI numeri divisibili sono %ld su %ld cioé il %u per
cento",nonprimi,campo2,perc_divisibili);
printf("\nSono stati eseguiti %.0f calcoli in %d secondi; potenza dei
computer! {:-D\n",calcoli,durata);
return 0;
}
L'ho limitato a 
2147000000
 per adesso(anche perchè c'ha messo un'ora e mezzo
a calcolarmi quanti primi ci sono da 5 a 30000000...... :D)....
Calcola i numeri primi tenendo conto del fatto che "dato un numero n , tale
numero è primo se non è divisibile per nessun numero primo inferiore alla
radice di n..."(anche se non ho capito come implementarlo del tutto: io
praticamente calcolo tutti i numeri, primi e non primi inferiori alla radice
di n: tu sai come fare? Risparmierei un sacco di tempo macchina!)...
Ho dato un'occhio anche ai possibili metodi statistici per risolvere il
problema, ma ci ho capito ben poco e immagino il casino ad implementarli ;-)
Già che ci sei ti posso chiedere un paio di cose?
Se io volessi ampliare l'insieme degli interi( long) da 4.294.000.000 a
supponiamo 2 elevato 4000 come faccio? E' possibile?
Poichè i long occupano 4 byte (32 bit) così occuperebbero 500 byte l'uno...
C'è un equivalente dell'operatore modulo % nei double?

di n: tu sai come fare? Risparmierei un sacco di tempo macchina!)...
Direi che senz'altro puoi evitare i pari>2, poi, nel tuo caso, al passo n
hai giá determinato
quali sono i primi fino a n-1 quindi sei a posto.
F.

 C'è un equivalente dell'operatore modulo % nei double?
C'e` modf, ma ci fai la birra: i double non hanno neppure lontanamente
la precisione necessaria.
Alex

 la precisione necessaria.
Cioè?
Non ho capito: se fai 5%2 cogli int il risultato è 1.... Con i long invece?

 Non ho capito: se fai 5%2 cogli int il risultato è 1.... Con i long
invece?
Che c'entrano i long?  Quelli sono pure numeri interi.  Tu parlavi di
double.  Coi double, magari, ti viene 1.000000000000000000001, no...?
Alex

uno spreco tremendo di tempo di calcolo.
E' vero: ho implementato quello che dici tu(almeno spero):
#include <stdio.h>
#include <math.h>
#include <time.h>
# define MAX 2000000
main()
{
time_t inizio,fine;
long array[MAX]={2,3,5,7,11,13,17,19,23,
29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91,97,101};
long campo;
long verifica;
long i;
int contatore;
double calcoli=0;
int durata;
unsigned long perc_primi;
unsigned long perc_divisibili;
long primi=0;
long nonprimi=0;
long campo2;
FILE *fp;
fp=fopen("riassunto3.txt","a");
contatore=26;
printf("\nInserire il campo di numeri: ");
scanf("%ld",&campo2);
if((campo2<5) || (campo2>
2147000000
))
{
return main();
}
campo=5;
time(&inizio);
while(campo<=campo2)
{
 for(i=0;array[i]<=sqrt(campo);array[i++])
  {
   calcoli++;
   verifica=campo%array[i];
   if(verifica==0)
   {
    nonprimi++;
    break;
   }
  }
  if(verifica!=0)
   {
    if (campo>101)
     {
      contatore++;
      array[contatore]=campo;
     }
    primi++;
   }
 campo++;
}
time(&fine);
durata=difftime(fine,inizio);
perc_primi=((primi*100)/campo2);
perc_divisibili=((nonprimi*100)/campo2);
fprintf(fp,"\nI numeri primi sono %ld su %ld cioé il %u per
cento",primi,campo2,perc_primi);
fprintf(fp,"\nI numeri divisibili sono %ld su %ld cioé il %u per
cento",nonprimi,campo2,perc_divisibili);
fprintf(fp,"\nSono stati eseguiti %.0f calcoli in %d secondi; potenza dei
computer! {:-D\n",calcoli,durata);
fprintf(stdout,"\nI numeri primi sono %ld su %ld cioé il %u per
cento",primi,campo2,perc_primi);
fprintf(stdout,"\nI numeri divisibili sono %ld su %ld cioé il %u per
cento",nonprimi,campo2,perc_divisibili);
fprintf(stdout,"\nSono stati eseguiti %.0f calcoli in %d secondi; potenza
dei computer! {:-D\n",calcoli,durata);
return 0;
}
Le operazioni per calcolare i primi da 5 a 1.000.000 scendono da 67 milioni
e qualcosa a 14 milioni circa....
Come avrai visto ho dimensionato un array enorme, che mi permette di
eseminare un campo che va da 5 a 20 milioni di numeri circa....
Dopodichè tenta di scrivere oltre l'array e va in segmentation fault....
Avevo pensato di memorizzare i numeri primi in un file: ma la
lettura/scrittura è molto + lenta.....
Senza contare il fatto delle dimensioni del file....
Così compilato mi dà circa 8 mega di file eseguibile(magari con malloc
cambia qualcosa :-D )....
Comunque se l'unico mezzo è quello di memorizzare i numeri, allora è solo un
problema di ram....
Tu non conosci per caso qualche free-shell che ti dia a disposizione un po'
+ di 5 minuti di fila per processo?(tutte quelle che ho provato dopo un po'
ti killano il programma(non che abbiano tutti i torti, teardrop docet.....))
Ciao
Steve