Newsgroup: it.comp.lang.c
Titolo: Prima il numero...

... o meglio numero primo :-)
Innanzi tutto salve a tutti, poi avrei un problemino:
mi serve un algoritmo decentemente veloce per la generazione di numeri
primi.
Spiego meglio: dato un intero k, devo trovare qual'č il numero primo n piů
grande che possa essere rappresentato usando k bit.
es. per k==3  -> n==7 (intervallo da 1..7, escludendo i numeri pari >2)
            k==4 -> n==13 (intervallo da 1..15, escludendo i numeri pari>2)
ecc. ecc.
Ovviamente una ricerca a forza bruta non va bene visto che non ho intenzione
di aspettare sessantanni per sapere quale sia il numero primo piů grande
rappresentabile in, diciamo, 64 bit :-)
C'č qaulche trucco per "cominciare dalla fine" ed analizzare i numeri a
ritroso? (es. per k==4 verificare 15, poi scartare14, e fermarsi a 13).
In caso esistono che voi sappiate funzioni euristiche che mi dicano che un
numero sicuramente non č primo, in modo da tentare un approccio "brute
force" solo per i numeri "sospetti"?
Per ora ho pensato a qualcosa del tipo:
#define TRUE 1
#define FALSE 0;
int checkprime(unsigned long n)
{
    /* se č paro e non č 2, non č primo*/
    if ( !(n&1) && n!=2 ) return FALSE;
    /* se č in una mia tabella dei primi 1.000 numeri primi, č primo*/
    if (prime_lookup(n)) return TRUE;
    /*altrimenti tocca fare il lavoraccio, magari ricorsivo...*/
    .....
}
Per "fare il lavoraccio" pensavo di usare l'algoritmo di euclide con la
tabella dei primi mille e solo dopo usare la forza (bruta).
Ovviamente devo anche generalizzare quell' "unsigned long" in modo da
operare su un numero di bit arbitrario.
Qualcuno ha idee? Grazie in anticipo.
---
Bye, Fox.

rappresentabile in, diciamo, 64 bit :-)
Se fosse come dico io potrei dirtelo subito :
Dato 2^64 = 18447544074509251586, poiche' 64 e' pari si ha 
n = 2^64 - 3 = 18447544074509251583
Bada che la mia teoria prescinde da ogni dimostrazione ! ;)
Andrea Laforgia
---------------
(grattatio pallarum omnia mala fugit)
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

 primi.
Non c'era il "Crivello di Eratostene" o qualcosa di simile?
EMG

    if (prime_lookup(n)) return TRUE;
Perche' non controllare invece se abbia qualche radice al di sotto del limite
della sua radice quadrata, solo tra i numeri primi ?
Ho appena scritto il programma di seguito che calcola, in un tempo abbastanza
breve (sulla mia macchina non arriva neanche a 1 secondo ;), i primi 5000 numeri
primi :
#include <stdio.h>
#include <math.h>
typedef unsigned long  DWORD ;
int main()
{
    DWORD buffer_primi [5000] = { 2 } ;
    short i, j, buffer_indice = 0 ;
    DWORD n = 3, sqtree ;
    while (buffer_indice <= 4999)
    {
          sqtree = (DWORD) sqrt ( n ) ;
          for (i = 0, j = 0 ; buffer_primi[i] <= sqtree ; i++)
              if ( n % buffer_primi[i] )
                 ++j ;
              else
              {
                 --i ;
                 break ;
              }
          if (i == j) buffer_primi[++buffer_indice] = n ;
          n += 2 ;
    }
    for (i = 0; i < 5000; i++)
        printf("%4d) %lu\n", i, buffer_primi[i]);
    return 0 ;
}
Ovviamente un programma del genere ha lo svantaggio di consumare molta memoria
ma puo' tornare utile in qualche caso.


con x preferibilmente dispari.
No, scusate ho sbagliato :
In realta', nel ciclo, p non deve incrementare di 1, ma di uno step tale da
diventare il prossimo numero primo ...
cioe' p = 2, p = 3, p = 5, p = 7, p = 11, e cosi' via...


Se fosse come dico io potrei dirtelo subito :
Mi spiace, non posso dirtelo subito ;)


Ok ci siamo ;)
Mi ci sono messo d'impegno e ho capito che e' ragionevole pensare la questione
in questi termini :
Dato che ogni numero pari (quindi anche ogni potenza di 2) e' esprimibile come
la somma di 2 numeri primi dispari si ha che, dato k >= 3, il numero n da noi
cercato e' esprimibile come n = 2^k - p (dato che 2^k = n + p) dove p e' il
numero primo piu' piccolo da considerare perche' sia anche n primo.
Ora, come trovare p.
Il programma di seguito illustra come fare :
#include <stdio.h>
#include <math.h>
typedef unsigned long  DWORD ;
typedef int            BOOL  ;
const BOOL  T = 1 ;
const BOOL  F = 0 ;
DWORD pot2 ( int e )
{
      return ( ( e ) ? ( 2 * pot2 ( e - 1 ) ) : 1 ) ;
}
BOOL is_prime ( DWORD x )
/* x deve essere abbastanza grande */
{
    DWORD q = 3, isqt = (DWORD) sqrt ( x ) ;
    while ( q <= isqt )
    {
          if ( ! ( x % q ) ) return ( F ) ;
          q += 2 ;
          /* analizza solo i dispari (tra i pari > 3 non vi sono primi) */
    }
    return ( T ) ;
}
DWORD greatest_prime ( unsigned k )
{
      DWORD max = pot2 ( k ) ;
      DWORD q = 1 ;
      BOOL found = F ;
      while ( ! found )
      {
            if ( is_prime ( q ) && is_prime ( max - q ) )
            {
               found = T ;
               continue ;
            }
            q += 2 ; /* q assume tutti i valori dispari */
      }
      return ( max - q ) ;
}
int main()
{
    unsigned k ;
    for ( k = 3 ; k < 32 ; k++ )
        printf("%4d -> %lu\n", k, greatest_prime( k ) ) ;
    return 0 ;
}
L'output che restituisce e' il seguente :
   3 -> 7
   4 -> 13
   5 -> 31
   6 -> 61
   7 -> 127
   8 -> 251
   9 -> 509
  10 -> 1021
  11 -> 2029
  12 -> 4093
  13 -> 8191
  14 -> 16381
  15 -> 32749
  16 -> 65519
  17 -> 131071
  18 -> 262139
  19 -> 524287
  20 -> 1048573
  21 -> 2097133
  22 -> 4194301
  23 -> 8388571
  24 -> 16777213
  25 -> 33554371
  26 -> 67108859
  27 -> 134217649
  28 -> 268435367
  29 -> 536870909
  30 -> 1073741783
  31 -> 
2147483647
Che questa volta e' corretto.
Come si puo' vedere, la ricerca del numero primo e' abbastanza veloce perche' si
adopera la tecnica di ricercare eventuali divisori tra i numeri dispari minori
della radice quadrata del numero 2^k.
L'efficienza massima, in termini di velocita', si avrebbe se al posto dei numeri
dispari si usassero i numeri primi, ma questo implicherebbe una complicazione
del programma, dovuta al fatto che bisognerebbe memorizzare un numero
_indeterminato_ di numeri primi da qualche parte con relativo ingente consumo di
memoria.
Adottando, invece, la tecnica del mio programma, se fosse k = 64 si avrebbe che
il numero di confronti massimo sarebbe sqrt(2^k)/2 ovvero 2^32/2 ovvero 2^31 =
2147483648
, il che, rispetto a 2^64, e' un numero accettabile.
Ovviamente, nel programma, e' facile che si trovi un numero primo dopo i primi r
confronti con r molto minore di questo limite.


Che questa volta e' corretto.
Ok, ok, c'era una volta un pastorello che, a furia di gridare "al lupo, al lupo"
per gioco, fece in modo che nessuno piu' gli credette quando chiese aiuto per
davvero, finendo sbranato.
Va bene, vi riconosco il diritto di farmi sbranare :)
Cercando di dimostrare che un numero pari e' sempre esprimibile come somma di
due numeri primi dispari, il che e' vero, mi sono accorto che cio' non implica
necessariamente che l'addendo maggiore sia quello piu' grande esprimibile con un
numero di bit pari all'intero del logaritmo base 2 del numero pari.
Questo vuol dire che va bene considerare 2^k come somma di due numeri dispari,
ma non necessariamente primi entrambi.
Vedi il caso di 2048 = 2^11 che e' esprimibile come 2029 + 19 (entrambi primi),
ma anche come 2039 + 9 (dei quali l'uno e' primo e l'altro no).
Ovviamente il valore da considerare e' 2039 dato che da 2040 a 2047 non vi sono
altri numeri primi.
Quindi, la routine greatest_prime() viene modificata come segue :
DWORD greatest_prime ( unsigned k )
{
      DWORD max = pot2 ( k ) ;
      DWORD q = 1 ;
      BOOL found = F ;
      while ( ! is_prime ( max - q ) )
            q += 2 ; /* q assume tutti i valori dispari */
      return ( max - q ) ;
}
Chiedo scusa per questo enorme pasticcio ;) 


Un bel di' Andrea Laforgia scrisse:
AL> Dunque, io ho studiato un metodo mentre ero in bagno ;)
AL> 
AL> Prova ad applicare il seguente algoritmo di generazione "istantanea" :
AL> 
AL> Dato k >= 3 : 
AL> 
AL> se k e' dispari allora n = 2^k - 1 ;
AL> 
AL> se k e' pari allora n = 2^k - 3 ;
AL> 
eh eh eh... il bagno... :-)
Comunque, mi rammarica dirlo, la formula bruta non basta :-(
Ecco infatti l'output del mio prog.
3 -> 7 e' primo! :)
4 -> 13 e' primo! :)
5 -> 31 e' primo! :)
6 -> 61 e' primo! :)
7 -> 127 e' primo! :)
8 -> 253 non e' primo! :(
        251 e' invece primo! :)
9 -> 511 non e' primo! :(
        509 e' invece primo! :)
10 -> 1021 e' primo! :)
11 -> 2047 non e' primo! :(
        2039 e' invece primo! :)
...
AL> Dato 2^64 = 18447544074509251586, poiche' 64 e' pari si ha 
AL> 
AL> n = 2^64 - 3 = 18447544074509251583
AL> 
si potrebbe, ora, testare se n e' indivisibile per ciascuno
dei p compresi tra 3 e sqrt(n).
L'ho fatto... e posto la soluzione di seguito :-)
#include <stdio.h>
#include <math.h>
int primo (int n) {
        int i, r;
        r = (int) sqrt (n);
        for (i = 3; i < r; i++)
                if (! (n % i)) return 0;
        return 1;
}
main () {
        int k, n;
        for (k = 3; k < 32; k++) {
                printf ("%d -> ", k);
                n = (int) pow (2, k);
                if (k % 2) --n;
                else n -= 3;
                if (primo (n)) printf ("%d e' primo! :)\n", n);
                else {
                        printf ("%d non e' primo! :(\n", n);
                        for (; ! primo (n) && n > 2; n-=2) ;
                        printf ("       %d e' invece primo! :)\n", n);
                }
        }
        return 0;
}
Ovviamente, purtroppo, funziona solo per interi fino a 32 bit... (31) :-(
Bisognerebbe creare un tipo di dati piu' grosso... :)
Comunque, si puo' sempre vedere cosa hanno da dire, a proposito, su
it.scienza.matematica :-)
-- 
"I cretini sono sempre piu' ingegnosi delle precauzioni che si prendono per
impedir loro di nuocere", corollario 3 alla legge di Murphy
-- 
Emanuele Cesena
em...@iol.it
          occhio all'antispam NOSPAM!
http://www.geocities.com/SiliconValley/Grid/8879

(grattatio pallarum omnia mala fugit)
:-)) Lo ricorderò.
---
Bye, Fox.

Non c'era il "Crivello di Eratostene" o qualcosa di simile?
Giuro su quello che vuoi di non averlo mai sentito. Ho fatto qualche
ricerca - sia cartacea che su web - ma questa proprio, come dicono gli
anglofoni - never covered (mai coperta :-) ).
Non è che puoi darmi più info?
Invece mi stava venendo in mente che per numeri molto grandi potrebbe
convenire tentare la radice quadrata (se un numero è un quadrato perfetto,
sicuramente non è primo). Dovrei trovare però anche li un algoritmo veloce
(spezzando il numero n in tronconi da 32 bit, come faccio ad usare le
funzioni usuali? Vatti poi a fidare delle approssimazioni del floating
point, mi serve qualcosa che lavori direttamente sugli interi.)
Mentre scrivo mi sta anche venedo in mente che se n = a * b + r (dove r è il
resto della divisione per b) possibile che non ci sia un appiglio che mi
dica - esaminado a, b ed r - qualcosa sull'essere primo di n? Verrebbe
mooolto comodo per b == 2^32 ;-) (o anche semplicemente se a == b - quadrato
non perfetto).
Boh, devo lavorarci un po. C'è un news dedicato alla matematica?
---
Bye, Fox.

 Giuro su quello che vuoi di non averlo mai sentito.
Ho ritrovato l'algoritmo. Non so se può essere accettabile in quanto
necessita di una matrice di dimensione pari al numero massimo che si
vuole esplorare diviso per otto. Praticamente si rappresentano i numeri
con una matrice di bit. Il valore 0 identificherà (ad esempio) un numero
non primo e il valore 1 un numero primo. Si contrassegnano inizialmente
come non primi tutti i pari maggiori o uguali a quattro e primi tutti
gli altri. Poi si impostano due cicli di questo tipo:
for ( i = 3; i <= MAX / 2; i += 2 )
    if ( primo( i ) )
        for ( j = i * 3; j <= MAX; j += i * 2 )
            imposta_non_primo( j );
dove la funzione primo( n ) accede al bit ennesimo e imposta_non_primo(
n ) imposta a zero il bit ennesimo.
Fammi sapere se ti soddisfa. Eventualmente prenditela con Eratostene. A
proposito: in inglese crivello si dice sieve...
EMG

Bisognerebbe creare un tipo di dati piu' grosso... :)
Be', sulla tua macchina un "int" puo' essere di 32 bit, mentre sulla mia di 64,
chi puo' dirlo ?
Forse, per maggiore sicurezza (vedi portabilita'), sarebbe meglio definire n
come "unsigned long" al posto di "int".
Comunque il tuo programma implementa lo stesso sistema del mio, postato
precedentemente in questo stesso thread. ;)
Andrea Laforgia
---------------
(grattatio pallarum omnia mala fugit)


non perfetto).
Ogni numero intero e' del tipo n = a * b + r (con vincolo (a*b != 0) ).
Per un numero primo si aggiunge un ulteriore vincolo :
Esistono solo due triple (a, b, r) che soddisfano la formula e sono (1, n, 0) e
(n, 1, 0).
Ma, dato n, si puo' dimostrare questa unicita' solo accertandosi che nessuna
tripla del tipo (a, b primo < [sqrt(n)], 0) soddisfi l'equazione e, quindi, solo
implementando un ciclo.
Purtroppo per noi, non e' possibile individuare i numeri primi usando regole
deterministiche, ma solo per confronto diretto, in quanto si potrebbe dire che i
numeri primi si collocano tra gli interi in modo _quasi_ casuale. 


 numeri primi si collocano tra gli interi in modo _quasi_ casuale.
Hai fatto bene a dire 'quasi'. Infatti ricordo benissimo che esiste uno
studio del matematico Ulam che mostra come, in certe condizioni, i
numeri primi, se graficati, diano luogo ad una figura quadrata ben lungi
quindi dall'essere casuale. Ne sai qualcosa di più?
EMG

quindi dall'essere casuale. Ne sai qualcosa di piy?
E' vero, ricordo anch'io qualcosa del genere.
Non so, pero', se stiamo parlando della stessa persona.
Mi ricordo di un matematico che ad una conferenza si stava annoiando a morte e
cosi', per ammazzare il tempo, si mise a disegnare su un foglio a quadretti i
numeri interi a partire da 1, in modo da formare una specie di spirale quadrata.
Presto' cura nel cerchiare, qualora li avesse trovati, i numeri primi.
Ricordo che egli fu sorpreso nel notare come i numeri primi si disponessero
secondo certe posizioni nei quadretti, tali che, ad una vista piu' ampia,
sarebbero apparsi tutti su rette parallele alle diagonali di un quadrato.
Ma non so che frutti abbia dato l'analisi matematica del problema.
Che io sappia non esistono in matematica regole discriminanti immediate per i
numeri primi.
Andrea Laforgia
-------------------------------------


force" solo per i numeri "sospetti"?
Se ti interessa un metodo veloce, ma probabilistico, puoi guardare
l'Algoritmo P in "The art of computer programming" di D.E.Knuth
(vol. 2, 4.5.4).
Ciao,
	Fabio

>Bisognerebbe creare un tipo di dati piu' grosso... :)
AL> 
AL> Be', sulla tua macchina un "int" puo' essere di 32 bit, mentre sulla mia di 64,
AL> chi puo' dirlo ?
AL> 
nessuno lo puo' dire, ma penso sia abbastanza chiaro quello che volevo dire...
AL> Forse, per maggiore sicurezza (vedi portabilita'), sarebbe meglio definire n
AL> come "unsigned long" al posto di "int".
AL> 
ok... pero' c'e' sempre un max relativamente basso.
AL> Comunque il tuo programma implementa lo stesso sistema del mio, postato
AL> precedentemente in questo stesso thread. ;)
AL> 
certo, ma quando ho scritto il mio msg il tuo prog. era quello a cui ho replicato,
senno' nno perdevo tempo a scrivere il mio msg ;-)
bye!
-- 
"La fortuna bussa sempre alla porta al momento sbagliato", precetto di
Ducharme


Un bel di' Andrea Laforgia scrisse:
AL> Che io sappia non esistono in matematica regole discriminanti immediate per i
AL> numeri primi.
AL> 
A proposito, se puo' interessare, so che ci sono algoritmi anche per stabilire
che "un numero e' primo con probabilita' p"... pero' non so altro :-)
Ciao!
-- 
"Il lavoro d'equipe e' essenziale. Ti permette di dare la colpa a qualcun
altro", ottava regola di Finagle


senno' nno perdevo tempo a scrivere il mio msg ;-)
Non c'era alcun programma in quel messaggio ;)


dei p compresi tra 3 e sqrt(n).
Sì, come dicevo ad Andrea in privato sono giunto alla dimostrazione di ciò
riflettendoci nei ritagli di tempo. Meglio ancora: basta considerare solo i
p compresi tra 3 e sqrt(n) _che siano primi essi stessi_.
Può sembrare una definizione ricorsiva (ed in parte lo è) ma basta allocarsi
una tabella di primi e riempirla dinamicamente. Mi spiego meglio.
Se stiamo testando 1237, possiamo in realtà provare a dividerlo per i numeri
p tra 3 e sqrt(1237) == 35. Immagianiamo ora di avere una tabella con i
seguneti primi:
3,5,7,11,13,17. Potremmo testare solo questi (saltando il 9 ed il 15) e
trovare tra quelli mancanti (da 19 a 35) quelli primi e metterli in tabella.
La prossima volta che ci troveremo a controllare se i numeri tra 1 e 35
dividano n, sapremo già che occorre provare solo quelli tra questi primi, e
sapremo già quali sono.
Segue codice d'esempio:
typedef unsigned long ulong;
typedef int    bool;
#define false 0
#define true 1
unsigned inlist;
ulong* primelist;
int check_prime(ulong n, int start)
{
    ulong high_div = (ulong) sqrt(n);
    ulong j_div;
    int i, j, k;
    bool j_prime;
    /* controlliamo quelli già in tabella a partire dallo start-esimo... */
    for (i=start; i<inlist && primelist[i] <= high_div; i++)
        if(n % primelist[i] == 0) return false;
    /*
         troviamo i primi tra i rimanenti con l'algoritmo "classico"
         solo fino a dove serve
    */
    for ( j = primelist[i-1]; j<=high_div; j+=2 )
        j_div = (ulong) sqrt(j);
        j_prime = true;
        for(k=3; k <= j_div; k+=2)
             if (j % k == 0) {
                j_prime = false;
                break;
             }
        if (j_prime) {
            add_prime(j);
            if (n % j == 0) return false;
        }
    }
    return true;
}
funziona particolarmente bene per ricerche in sequenza (la tabella primelist
si suppone ordinata, se ne occupa add_prime(), ed inizializzata) in cui si
debbano testare molti numeri. Mano a mano l'esecuzione dominante sarà il
primo for.
(necessita ancora di qualche affinamento :-) )
Sto pensando anche a "come" scegliere i numeri da testare nel caso si
vogliano generare tutti i primi tra 1 e 2^k (con k numero di bit). (non mi
serve, ma mi sembra interessante)
Questo è l'approccio che utilizzo:
int main()
{
 ulong n;
 printf("Ricerca in corso...\n");
 primelist = (ulong*) malloc(alloc * sizeof(ulong));
 primelist[0] = 1;
 primelist[1] = 2;
 primelist[2] = 3;
 primelist[3] = 5;
 primelist[4] = 7;
 inlist = 5;
 /*
  30 è il "passo" di scansione. Dal momento che vogliamo saltare
  i divisibili per 2,3 e 5 il passo sarà 2*3*5 == 30.
  Eliminiamo poi dal check quei numeri che sicuramente non sono primi
  perché divisibili per 2,3 e 5.
  es. cominciamo da 11 (dovremmo cominciare da 6 a rigore, ma 7 lo
  fissiamo nella tabella dei primi per evitare un controllo inutile e
sappiamo che il prox
  primo è 11)
  controlliamo 11,13,17,19,23,29,31,37 e puntiamoci su 41.
  (in questo modo possiamo controllare solo 8 "sospetti" su 30)
  dato che è ciclico controlleremo tutti i numeri 11 + k*30
              13 + k*30
              17 + k*30
              19 + k*30
              23 + k*30
              29 + k*30
              31 + k*30
              37 + k*30
         con k = 0,1,2...
 */
 for (n = 11; n <= limit-30; n+=4) {
  check_prime(n, 4); /* 11 comincia il check da primelist[4] == 7, visto che
stiamo escludendo i divisibili per 2,3,5 */
  n+=2;
  check_prime(n, 4); /* 13 */
  n+=4;
  check_prime(n, 4); /* 17 */
  n+=2;
  check_prime(n, 4); /* 19 */
  n+=4;
  check_prime(n, 4); /* 23 */
  n+=6;
  check_prime(n, 4); /* 29 */
  n+=2;
  check_prime(n, 4); /* 31 */
  n+=6;
  check_prime(n, 4); /* 37 */
 }
 for ( ; n <= limit; n+=2) {
  check_prime(n, 2);
 /* comincia il check da primelist[2] == 3, visto che stiamo escludendo i
divisibili per 2 */
 }
/*
.... trattamento dei dati ottenuti
*/
return 0;
}
Sto cercando di generalizzare la cosa... vedremo.
---
Bye, Fox.

che "un numero e' primo con probabilita' p"... pero' non so altro :-)
Ci sono test mediante i quali si puo' stabilire se numeri con una certa
probabilita' di essere primi siano primi o meno.
In realta', il Crivello di Eratostene, suggerito da EMG, e da me applicato nel
programma, e' valido per la ricerca di numeri primi entro un certo intervallo,
in quanto e' un metodo che, col crescere dell'estremo superiore, puo' impiegare
troppo tempo.
Esiste un test, per stabilire se un numero ha una buona probabilita' di essere
primo o se non lo e' con certezza.
La regola e' questa :
Supponendo di scrivere n-1 = 2^s * d dove d e' dispari ed s >= 0  si ha che :
n e' un primo di base a con probabilita' forte (e si indica come a-SPRP) se e'
verificato che a^d = 1 (mod n) oppure che (a^d)^(2^r) = -1 (mod n) per  
0 =< r < s.
Tutti gli interi n > 1 per i quali il test fallisce non sono primi.
Gli interi per i quali il test e' soddisfatto *potrebbero* essere primi.
Ad esempio si ottiene che :
2047, 121, 781 e 25 sono rispettivamente 2-SPRP, 3-SPRP, 5-SPRP e 7-SPRP. 
Ma sono composti.
Vincolando il risultato si puo' ottenere la certezza della primalita' del numero
o meno.
In particolare e' stabilito che 
se n < 1,373,653 ed esso e' nel contempo 2-SPRP e 3-SPRP, allora e' primo. 
se n < 25,326,001 ed e' un 2, 3 e 5-SPRP, allora e' primo. 
.
.
se n < 9,080,191 ed e' 31 e 73-SPRP, allora e' primo. 
se n < 4,759,123,141 ed e' 2, 7 e 61-SPRP, allora e' primo. 
se n < 1,000,000,000,000 e' 2, 13, 23, e 1662803-SPRP, allora e' primo.


p compresi tra 3 e sqrt(n) _che siano primi essi stessi_.
Attenzione : sqrt(n) deve essere compreso : 3 < p <= sqrt(n).
In ogni caso, vorrei proporre un metodo molto sbrigativo per calcolare i primi
entro un certo limite, un metodo piu' veloce di quello di Eratostene.
In pratica, si parte dal principio opposto a quello di ricerca.
Ovvero, supponiamo una tabella di 20000 booleani, inizialmente inizializzati a
TRUE.
Si comincia da 3 fino a [sqrt(20000)] e si escludono dalla tabella (segnandoli
magari con un FALSE) tutti i multipli dei primi trovati. 
Mi spiego meglio col programmino di seguito che esegue il calcolo dei primi
20000 primi (gioco di parole ;), giudicate voi la velocita' ;) 
#include <stdio.h>
#include <string.h>
#include <math.h>
typedef unsigned char BOOL ;
typedef unsigned int  WORD ;
static const BOOL true  = 1 ;
static const BOOL false = 0 ;
static const WORD max   = 20000 ;
int main()
{
    BOOL bool_array [ max ] ;
    WORD upper_limit = (WORD) sqrt(max) ;
    WORD j, k, p ;
    memset ( bool_array, true, max ) ;
    for ( k = 2 ; k <= upper_limit ; k++ )
        if ( bool_array [ k - 1 ] )
           for (j = 2 ; (p = k*j) <= max ; j++)
               bool_array [ p - 1 ] = false ;
    for ( k = 0 ; k < max ; k++ )
        if ( bool_array [ k ] ) printf("%d\n", k+1);
    return 0 ;


>senno' nno perdevo tempo a scrivere il mio msg ;-)
AL> 
AL> Non c'era alcun programma in quel messaggio ;)
AL> 
c'era l'output :-)
-- 
"Gli amici vanno e vengono, i nemici si accumulano", motto di Jones


(vol. 2, 4.5.4).
Giusto, sai se c'è un'edizione in rete? Altrimenti mi tocca andare in
biblioteca.
---
Bye, Fox.
P.S. Grazie anche a te.

numeri primi.
Dalle mie ricerce posso dirti che č stato dimostrato che nessuna espressione
polinomiale puň generare solo numeri primi. Sto cercando di capire quale sia
la percentuale di "falsi allarmi" generabili con le varie tecniche (vedi
metodo del "passo" ciclico in msg a Ema da Tin, su 65000 valori ne controllo
solo 17000).
---
Bye, Fox.

proposito: in inglese crivello si dice sieve...
Sě, ho trovato qualche riferimento in un testo di analisi numerica, ma quel
nome non č mai saltato fuori. Ah, i greci.. :-))
---
Bye, Fox.
P.S. C'č un evidente errore, il primo for andrebbe letto:
    for( i=3; i <= MAX/3; i+=2)


questa riga va letta come:
        for ( j = primelist[i-1] + 2; j <= high_div; j+=2)    {
---
Bye, Fox.

Andrea Laforgia (
andrea_...@bigfoot.com
) wrote:
[ snip ]
: In ogni caso, vorrei proporre un metodo molto sbrigativo per calcolare i 
: primi entro un certo limite, un metodo piu' veloce di quello di Eratostene.
Guarda che il metodo da te proposto (partire da un array di tutti 1, 
eliminare man mano i multipli dei primi trovati, ecc.) e' quello del 
crivello di Eratostene (es. 'Algorithms in C' di Sedgewick, pag. 84).
Ciao ciao,
Andrea
-- 
"...Unix, MS-DOS, and Windows NT (also known as the Good, the Bad, and 
 the Ugly)."
(by Matt Welsh)

     for( i=3; i <= MAX/3; i+=2)
Dici? Beh, se č cosě, ancora meglio: sarebbe piů veloce. Mi
spiegheresti, perň, il perché?
EMG

 uscita una decina d'anni fa su Le Scienze).
Se riesci a sapere il numero esatto dimmelo. Ho tutti i numeri dal
1986...
EMG

>p compresi tra 3 e sqrt(n) _che siano primi essi stessi_.
AL> 
AL> Attenzione : sqrt(n) deve essere compreso : 3 < p <= sqrt(n).
AL> 
Fra l'altro (una precisazione banale) si puo' troncare sqrt(n) all'intero.
AL> Si comincia da 3 fino a [sqrt(20000)] e si escludono dalla tabella (segnandoli
AL> magari con un FALSE) tutti i multipli dei primi trovati. 
AL> 
Non vorrei sbagliarmi... ma il programma non inizia da 2?? ;)
A parte questo, secondo te (voi), non converrebbe considerare direttamente solo
i numeri dispari??
ciao!
-- 
"8. Cammina sempre a gran velocita' quando sei fuori del tuo ufficio:
eviterai un gra numero di domande sia dai subordinati che dai superiori",
dal decalogo di Spark per il giovane manager


crivello di Eratostene (es. 'Algorithms in C' di Sedgewick, pag. 84).
Mi riferivo a quello che va per confronto, non a quello di Eratostene.


solo 17000).
Per i numeri piccoli e' sempre meglio usare il crivello di Eratostene.
Con 65000 valori controlleresti solo i primi <= 254 !


c'era l'output :-)
Ma non era il programma di cui parlavo io !!!!


i numeri dispari??
No, perche' 9, ad esempio, viene escluso, in quanto multiplo di 3.
Il mio programma fa attenzione a considerare solo i numeri primi e non tutti i
dispari.
All'inizio la situazione e' questa :
1  2  3  4  5  6  7  8  9 10 11 12  ...
1  1  1  1  1  1  1  1  1  1  1  1  ...
A partire dal 2 vengono eliminati tutti i suoi multipli e si ha :
1  2  3  4  5  6  7  8  9 10 11 12  ...
1  1  1  0  1  0  1  0  1  0  1  0  ...
Poi vengono eliminati i multipli di 3 e cosi' via ... 
1  2  3  4  5  6  7  8  9 10 11 12  ...
1  1  1  0  1  0  1  0  0  0  1  0  ...
Se un numero e' gia' a 0 non viene considerato ed in questo caso si salta il 4 e
si passa al 5 e cosi' via...
Alla fine quelli che rimangono sono solo i primi.


>i numeri dispari??
AL> 
AL> No, perche' 9, ad esempio, viene escluso, in quanto multiplo di 3.
AL> 
mi sono espresso male. Intendevo:
[Reciclo parole mode ON]
All'inizio la situazione e' questa :
 
1  3  5  7  9 11 ...
1  1  1  1  1  1 ...
A partire dal 3 vengono eliminati tutti i suoi multipli e si ha :
1  3  5  7  9 11 ...
1  1  1  1  0  1 ...
Se un numero e' gia' a 0 non viene considerato ed in questo caso non si salta il 4 
(perche' non c'e') e si passa al 5 e cosi' via...
Alla fine quelli che rimangono sono solo i primi.
[Reciclo parole mode OFF]
Ciao!
-- 
"Chi ha, prende", legge di ferro della Distribuzione
-- 
Emanuele Cesena
mi e' saltata la mail!! Per favore, scrivete per ora a
 
su...@geocities.com
(occhio sempre all'antispam NOSPAM)

>(vol. 2, 4.5.4).
 FC> Giusto, sai se c'è un'edizione in rete? Altrimenti mi tocca andare in
 FC> biblioteca.
 Che io sappia no, ma se mi fornisci il tuo indirizzo email ...
Ciao,
	Fabio
:-)))))  "avere fede solo nella ragione e' proprio irrazionale"  :-)))))
(26-02-1999 03:05:00, it.cultura.ateismo "Re: Un prete parla agli atei")

Alla fine quelli che rimangono sono solo i primi.
Tutto giusto, perň si possono saltare i pari, soprattutto i multipli pari, a
priori. Mi sono permesso di adattare il tuo codice per farlo, vedi msg di
risposta a EMG poco piů avanti.
Quel che ne č venuto fuori č il metodo piů veloce che abbia trovato finora e
funziona benone per numeri piccoli (< 2^32).
---
Bye, Fox/ le ultime due cifre del mio anno di nascita formano un numero
primo :-).

spiegheresti, però, il perché?
Certamente. Dal momento che l'unica funzione che modifica la matrice è la
imposta_non_primo e che questa dipende da j, basta far vedere che il secondo
for non viene eseguito per i > MAX/3.
Semplice: posto i = MAX/3 + 1 (senza perdita di generalità), il secondo for
si leggerebbe
for (j= i*3; j <= MAX; j+=2)
e sostituendo i:
for (j = (MAX/3 + 1) * 3; j <= MAX; j+=2)
cioè:
for (j = MAX + 3; j <= MAX; j+=2)
Dato che (MAX + 3 <= MAX) è sempre false, ecco che far andare i oltre MAX/3
è perfettamente inutile (intendiamoci: funziona lo stesso ma è
inefficiente).
Unendo questo codice con l'approccio di Andrea (Laforgia) di qualche
messaggio fa, otteniamo la seguente versione ottimizzata:
[...]
/*     ci interessa trovare almeno un divisore per i numeri non primi,
        basta quindi fermarsi a sqrt(MAX)
*/
upper_limit = sqrt(MAX);
/*
     facciamo fuori i pari...
     N.B. si suppone MAX >3 e numero pari
*/
BOOL* p_bool = bool_array;
for (i=0; i < MAX/2; i++)    {
    *p_bool++ = true;
    *p_bool++ = false;
}
/* salvando il 2 */
p_bool[1] = true;
/* prendiamo il mitra e cominciamo a crivellare...*/
for (k=3; k <= upper_limit; k+=2)
    if(bool_array[k-1])
        for ( p = k*3; p <= MAX; p+= k*2)
            bool_array[p-1] = false;
/* rapporto danni :-) */
[...]
Se poi non ci si fida dell'ottimizzazione del compilatore, si può scrivere
il crivello come segue:
/* prendiamo il mitra e cominciamo a crivellare...*/
for (k=3; k <= upper_limit; k+=2)
    if(bool_array[k-1])    {
        k_2 = k << 1;     /* moltiplichiamo per due in modo veloce e fuori
dal ciclo*/
        for ( p = k + k_2; p <= MAX; p+= k_2)
            bool_array[p-1] = false;
    }
dove ovviamente k + k_2 equivale a k * 3.
Rispetto a quello di Andrea ha il pregio di saltare _a priori_ i multipli
pari, rispetto al crivello classico ha il pregio di fermarsi a sqrt(MAX)
Funziona particolarmente bene per MAX <= 2^32. Poi comincia a diventare
lento (e comunque l'occupazione di memoria si fa sentire).
---
Bye, Fox.

...

Me l'ha appena portato, si tratta di un "Le Scienze Quaderni n. 45" -
dicembre 1988.
L'articolo si intitola "Gli schemi dei numeri primi e la legge forte dei
piccoli numeri", firmato Martin Gardner (pag..45).
E' più che altro una articolo divulgativo che - in sostanza - richiama a
fare attenzione a congetture che sembrano andare per piccoli numeri e che si
dimostrano poi false.
Aspe', alla fine c'è un riferimento a "Le Scienze" n. 158 - ottobre 1981.
Sono 4 pagine con qualche illustrazione. L'offerta di scanning rimane valida
:-)
---
Bye, Fox.

Con 65000 valori controlleresti solo i primi <= 254 !
Assolutamente d'accordo.
---
Bye, Fox.

 Sono 4 pagine con qualche illustrazione. L'offerta di scanning rimane valida
Lascia perdere. Non č che poi l'argomento mi interessi cosě tanto.
EMG

 Certamente. [...]
Grazie.
EMG

p_bool[1] = true;
Dannata distrazione, la riga sopra va letta:
bool_array[1] = true;
---
Bye, Fox/altrimenti succede un casino.

priori.
Avete ragione ! ;)


 upper_limit = ulong( sqrt(MAX) );
Credo che il cast sia ridondante.


Credo che il cast sia ridondante.
Col cygnus (gcc win32) sì, con VC mi da un warning, e io odio i warning....
:-)
---
Bye, Fox/Per campare tocca scrivere win32 e non linux :-|.