C++, Java - Numere prime. Algoritm multithreading. Optimizari

Am nevoie de ajutor intr-o problema de Java (clasic)ori C++. Trebuie sa calculez numerele prime , cu fire de executie, pana la o anumita valoare. Asta am facut , dar intr-un mod neoptim . Adica , am dat fiecarui fir un segment egal de numere (consecutive) pe care sa le verifice . Si fiecare fir isi facea treaba independent de celelalte . Adica : verifica (calculand restul impartirii la 2 , 3, 4, 5etc...) daca nr. e prim ,daca da scria intr-un vector comun etc.... NEOPTIM!!! /ce_carnat

Acum , e suficient sa "stiu" ca nr. nu e par pt. a nu-l mai imprti cu multiplii de 2 , nu???!!! De asemenea e suficient sa caut divizori ai nr. pana la radicalul acelui numar (sgrt(n)) . DE ce ??? Daca nu divizor nu e gasit in divizor1 sgrt(nr). pt ca ar trebui sa existe si un alt divizor2 ma mare decat decat divizor 1  ai divizor 1 *divizor 2 =nr , da??!! . Ori div1 si div2 sunt mai mari ca sgrt(nr) deci div1*div2>nr Absurd .Iar fiecare fir trebuie sa caute divizori in vectorul de nr. prime comun  etc.... I'm lost ! Nu pot gasi un algoritm optim de implementare a firelor pt. nr . prime . Poate voi ????  
Mai  sunt si newbie asa ca ceva cod sursa ar prinde f bine!!!., ori ceva site de doc,sources etc.. :kiss:

Nu ma intereseaza ciurul lui Eratosthene -care e doar algoritmul de "primuire" ci firele

... pai dupa cum spui tu problemele de optimizare sunt in primu' rand la algoritm, mai putin la programarea lui ... ceea ce inseamna ca cea mai mare parte a optimizarilor vor veni MATEMATIC ... din punct de vedere al programarii, cel mult poti sa faci niste optimizari pe la managementu' memoriei si sa asiguri o comunicare mai buna intre firele de executie, eliminandu-se astel niste verificari in plus ...

Cretze :cya:

Fii antena aici!

Testul de primalitate Miller-Rabin:

n-nr>2 impar care se testeaza daca e prim
s-proba,s apartine {1...n-1},s trebuie sa fie cel putin (n-1)/2,
adica s e nr de incercari

Miller-Rabin(n,s)
1.pentru j=1,pana la s executa
2.           a=RANDOM(1,n-1)
3.           daca PROBA(a,n) atunci
4.                      returneaza COMPUS
5.returneaza PRIM

PROBA(a,n)
1.fie (B(k) B(k-1)......B(0)) reprezentarea binara a lui n-1
2.d=1
3.pentru i=k,pana la 0,pas -1 executa
4.           x=d
5.           d=(d*d) mod n
6.           daca d=1 si x!=1 si x!=n-1 atunci
7.                     returneaza ADEVARAT(adica nr e compus)
8.           daca b(i)=1 atunci
9.                      d=(d*a) mod n
10.daca d!=1 atunci
11.          returneaza ADEVARAT
12.returneaza FALS(adica nr e prim)

Algoritmul asta e cam prtentios in sensul ca e folosit in criptografie la testarea nr prime mari,dar sper sa te ajute.
Raman la latitudinea ta implementarea si generarea
nr aleatoare (alegerea functiei RANDOM).Daca vrei mai multe detalii le gasesti in "Introducere in algoritmi" de Cormen,
Leiserson si Rivest(Referitor la Miller-Rabin).In Knuth gasesti
tratata partea cu generarea numerelor aleatoare.
Cam atat ... :cool:

un numar x este prim  dc el nu se imparte la 2,3,4,,,, radical din el:
sa ti scriu un prg mic, nu e compilat asa ca nu sariti dc uit vreo virgula ceva, doresc sa arat algoritmul....

var x:word; // am folosit word pt ca este si in c++ si se lucreaza pana la 65536 parca
     e:boolean; // in  c nu stiu dc s-a bagat boolean, dc nu poti folosi un tip int sau shortint.... si lucrezi cu 0-> false si 1=> true

x:=987;
e:=true;//sa presupunem ca nr x este prim
for i:=2 to sqrt(x) do   // var i ia valori de la 2 pana la radical din x
if (x mod i)=0 then begin// imparte x la i si imi returneaza restul
                               e:=false;//numarul nu este prim
                               break;//iese din ciclul for pt ca numarul e clar ca nu prim si nu mai pierdem timp pt a verifica si cu alte numere
                             end;
afisez ca numarul x nu este prim

in cazul in care pui sa verifici dc numerele in val a si b sunt prime faci in asa  fel incat sa le dai numai pe cele impare:
,dc x este par scrii x++ apoi,
x sa fie numai impar x:=x+2 si astfel obtii numar impar;si dai la acest algoritm de mai sus

acum implementezi acest algoritm in thearturi... nu este f greu cel putin in delphi pt ca nu prea ai nevoie de restrictii, creezi un threat cu algoritm acesta si pui sa afisese pe ecran cand termina numarul si dc este sau nu prim


cu acest algoritm pe un calc mediu optii numerele prime de la 2...1 mil sa zic intr-un timp f scurt