Newsgroup: it.comp.lang.c
Titolo: generatore di numeri primi minori di N

Salve, basandomi su quello che fece Eratostene, ho fatto un piccolo
programma in C per la generazione di numeri casuali. Tuttavia credo sia
lento ed esistano metodi migliori per generare numeri primi. Vi posto il
codice (non fate caso a come è strutturato :P):
#define MAXNUM 100
typedef struct {
  int n;
  unsigned char flag;
} num;
int find(int n);
num cri[MAXNUM];
int main()
{
  int i, n=2, stop=0;
  for(i=0; i<MAXNUM; i++)
  {
    cri[i].n = i;
    cri[i].flag = 0;
  }
  i=n;
  while(!stop)
  {
    stop = 1;
    for(i+=n;i<MAXNUM; i+=n)
    {
        if(cri[i].flag == 0)
        {
                cri[i].flag = 1;
                stop = 0;
        }
    }
    n = find(n);
    i=n;
  }
  for(i=2; i<MAXNUM; i++)
  {
    if(cri[i].flag == 0)
        printf("%d ", cri[i].n);
  }
  getchar();
  return 0;
}
int find(int n)
{
  n++;
  for(;n<MAXNUM; n++)
  {
    if(cri[n].flag == 0) return cri[n].n;
  }
}
Esistono metodi migliori, algoritmi che non necessitano particolari
conoscenze? Grazie in anticipo

 conoscenze?
Sì, io ho scritto questo per i numeri da 3 in poi (non proprio in C):
int get_bit(const ULONG i,const ULONG *x)
{ return (x[i>>5]>>(i&31)) & 1; }
void set_bit(const ULONG i,const ULONG v,ULONG *const x)
{
 v? x[i>>5] |= 1uL<<(i&31) : x[i>>5] &=~(1uL<<(i&31));
}
ULONG N=MAXNUM,nmax=(N+1)/2;
ULONG *const PR=new ULONG[nmax/32+1];
memset(PR,255,nmax/8+1);
 for(int i=0;i<nmax;i++)
  if(get_bit(i,PR)) {
   ULONG prime=i+i+3;
   for(int k=i+prime;k<nmax;k+=prime) set_bit(k,0,PR);
  }
// Qui fai qualcosa con i numeri primi trovati
// Il numero primo è i+i+3
 for(int i=0;i<nmax;i++) if(get_bit(i,PR)) S+=i+i+3;
 delete[] PR;
ULONG è unsigned long.
La mia versione ha il vantaggio di essere circa 4 volte più veloce e di
richiedere pochissima memoria.
Esistono metodi migliori (aventi una velocità impressionante con una
bassissima occupazione di memoria), ma richiedono conoscenze particolari.
Cristiano

> Sě, io ho scritto questo per i numeri da 3 in poi (non proprio in C):
forse in c++, piu' che non proprio in c!
;)

Salve, basandomi su quello che fece Eratostene, ho fatto un piccolo
Io conosco questo metodo....
#include <stdio.h>
#include <math.h>
#define MASSIMO 10
int primo(unsigned int numero);
int main()
{
unsigned int i;
for (i=1;i<MASSIMO+1;i++)
        if(primo(i))
                printf("%d\n",i);
return(0);
}
int primo(unsigned int numero)
{
int i;
if (numero < 3)
        return(1);
else
{
        for (i=2;i<sqrt(numero);i++)
                if (!(numero % i))
                        return(0);
        return(1);
}
}
naturalmente puoi ottimizzarlo, per esempio scartando tutti i numeri
pari maggiori di due ecc....

bassissima occupazione di memoria), ma richiedono conoscenze particolari.
Beh, se l'algoritmo e' il crivello, l'occupazione di memoria minima e'
quella.
Ciao
 Max

 quella.
Con il crivello, l'occupazione di memoria aumenta all'aumentare di MAXNUM.
Con altri sistemi, invece, la memoria occupata è costante e non supera
qualche migliaio di byte anche per MAXNUM fino a 64 bit.
Cristiano

qualche migliaio di byte anche per MAXNUM fino a 64 bit.
Hai qualche dritta, in proposito?
Ciao
 Max

 Hai qualche dritta, in proposito?
http://cr.yp.to/primegen.html
Il programma utilizza alcuni vettori di costanti più una struttura in cui
c'è ULONG buf[16][x]. Dalle prove che feci a suo tempo, ho trovato che x=512
dà il massimo della velocità (forse sempre a causa della cache).
Cristiano

dà il massimo della velocità (forse sempre a causa della cache).
Si, probabilmente ricade in qualche multiplo strano di qualche
larghezza di pagina...
Ciao
 Max

while i<=N do
Si, lo so, sono OT col linguaggio. Abbiate pazienza, ma al momento
avevo quello sotto mano...
Ciao
 Max

 il mio ci mette 2 minuti e 10 su un P3 a 800, occupando 62 MB.
Il mio impiega 69,5 s (però abbiamo cpu differenti) e occupa 62.500.000
byte.
Sei sicuro di far bene a fare "un'ulteriore operazione di shift a destra"
(come dici più sopra)?
Ciao
Cristiano

(come dici piů sopra)?
Si. In origine nell'array avevo flag per tutti i numeri e non solo
quelli dispari. Per indicizzare all'interno della casella prendevo i 5
bit meno significativi di i e generavo la maschera col bit a uno nella
posizione giusta con:
(1 << (i & 0x1f))
Nella nuova implementazione prendi i sei bit meno significativi
(maschero con 0x3f invece che con 0x1f), e di questi usi i 5 piu'
significativi (a questo serve il >>1):
(1 << ((i & 0x3f) >> 1))
Ciao
 Max