[matlab] ottimizzazione funzione numeri primi

[mr mojo]

ho scritto questa function banale che genera numeri primi, funziona ma se voglio calcolarli per esempio fino a $10^10$ ci mette un'eternità(infatti mi sembra debba fare circa $10^20$ operazioni)... qualcuno ha idee su come diminuire il numero di operazioni e quindi il tempo di esecuzione? anche un approccio totalmente diverso dal mio va bene...



x=zeros(n,1);x(1)=1;x(2)=2;x(3)=3;x(4)=5;x(5)=7;j=6;primo=0;
for i=8:n
for d=2:i/2
if (mod(i,d)>=1)
primo=1;
else
primo=0;
break;
end
end
if (primo==1)
x(j)=i;
j=j+1;
end
end
p=zeros(1,j);
for k=1:j
p(k)=x(k);
end

[kobeilprofeta]

se esistesse un metodo veloce per calcolare i numeri primi non sarei qua a quest'ora...

[mr mojo]

......
immagino che nessuno mi dia una formula per calcolarli, solo se qualcuno conosce un algoritmo un pò più veloce di questo che sfrutti altre proprietà

[vict85]

Dato che vuoi trovarli tutti direi di dare un'occhiata al Crivello di Eratostene.