023 Numere Prime

[•fluffy]

...

[Chris]

Buna!

 Am trimis o solutie la aceasta problema, imi intra in timp dar pentru testel 5-10 imi da wrong answer. Problema o rezolv cu : result = prime[k+1]^2 si pentru a calcula ce de-al k+1 lea nr prim folosesc ciurul lui eratostene. Mie mi se pare corecta rezolvarea (am testat-o cu un program brute-force si a mers pentri testele date de mine).
 E gresita ideea ?

[•zackk]

Al 100.000-lea numar prim e 1299709iar al 100.001-lea e 1299721. Daca l-ai ridica la patrat, ar rezulta un numar ce nu ar putea fi retinut nici de tipul long. Incearca sa simulezi inmultirea cu ajutorul vectorilor  

[Chris]

Stiu ca nu intra in long!!! Am folosit unsigned long long si nu mergea nici asa. (oricum am luat 100 de puncte - mi-am dat seama ca asta era problema si am implementat inmultirile cu numere mari). Ideea e ca 1 000 000 * 1 000 000 ar trebui sa intre in 64 de biti.
   Nu am inteles o chestie cu tipul long long din C ... Operatiile pe 64 biti sunt emulate Din cate stiu eu registrii generali ai microprocesorului  (eax, ebx, ecx, edx) sunt pe 32 de biti!!!

[vladut.forum]

ba nu... daca aflii corect acel numar care trebuie ridicat la patrat, intra in long long... (am luat 100), nu e necesar operatii pe nr mari

[•dobre]

Eu am rezolvat de mult problema,lucrez in pascal, si tin minte ca am facut inmultire pe numere mari, si am luat 100,  nu stiu cum e treaba cu C-ul, dar nu dureaza mult implementarea inmultirii(in cartea lui Francu este o implementare scurta scrisa in C  )...

[andreit1]

Nu este necesara inmultirea pe numere mari. Un long long in C si un int64 in Pascal sunt suficiente.

[•Stilgar]

imi poate spune cineva macar un test din testele 6-10 ca iau wa si nu stiu de ce. Nu vreau si output-u ci doar inputu ca la partea de debug o sa vad io cum fac.

[•filipb]

Pai na, sa spunem ca la testul 10 ai K = 100 000!... Mai verifica ciurul! Verifica daca toate numerele prime iti dau bine! Eu am facut asa: am generat toate numerele prime ( cu ciurul ) mai mici de X ( unde X e suficient de mare, de ex. 10 000 000 ), si am aflat al (K+1)-lea nr. prim! Ai grija k rezultatul sa fie pe 64 de biti. Si de exemplu dak ai ceva de genu' "long P;" unde P e numarul prim determinat, ca sa il ridici la patrat il convertesti la long long: fprintf(fout, "%lld\n", (long long)P * P);

[•Stilgar]

pai cam asa am facut si io cu un sir aux. care imi mem. primul pe a[0] al 101-lea pe a[1] ;al 201-lea pe a[2] etc. pt 100 001 lea nr prim ii bine ca cineva l-o afisat pe forum si ii la fel ca al meu.io lucrez cu k initial pentru ca pt k=0 gasesc 2; pt k=1 gasesc 3 etc. (pe care le ridic la patrat evident)

Cod:

i:=a[k div 100];
q:=i;
for j:=0 to k mod 100 do
  begin
    t:=true;
    if q=2 then
      q:=3 else
    while t do
      begin
        t:=false;
        if q mod 2=0 then t:=true else
        for r:=1 to trunc(sqrt(q)) div 2 do
          if q mod (2*r+1)=0 then
            begin
              t:=true;
              break;
            end;
         inc(q);
      end;
  end;
x:=(q-1)*(q-1);
writeln (f2,x:0:0);
close(f2);
end.

ideea ii ca reiau numaratoare de la cea mai mare val memorata pana la k (intotdeauna o sa-l numar si pe numarul care io stiu ca-i prim si atuntci la sf cand afisez (q-1)*(q-1) fac asa pentru ca dupa ce ies din while-u ala o sa am val cu unu mai mare decat cea cautata)
si x ii extended (adica pana pe la 18 cifre)

[•filipb]

Pai vezi! Banuiam eu ca aici ai gresit... Si eu am facut aceeasi greseala la OJI anu' asta de am fost al nu stiu catalea! NU CONTEAZA CA X este extended!!! Important este ca q nu este!!!
  Adica tu poti sa ai: "int i = 32000; long P; ".. Daca faci P = i * i, iti va da aiurea pentru ca rezultatul i * i este int. La tine q-ul trebuie sa fie si el extended! Astfel incat membrul drept sa fie calculat de tip extended!
  Daca nu ai gresit si in alta parte, acum ar trebui sa nu mai ai probleme...

[•Adriana_S]

la problema asta n-ar trebui specificat sa se gaseasca cel mai mic nr N care bla bla bla, dar sa fie diferit de 1? Ca dupa mine 1 nu este divizibil cu oricate numere prime si nici nu este prim(cum scrie si in enunt). Ma rog, stiu ca este evident dar totusi...