Imprimă pagina - 023 Numere Prime

Titlul: 023 Numere Prime
Scris de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:31:25

...

Titlul: 023 Numere Prime
Scris de: Chris din Septembrie 09, 2004, 19:00:46

Buna! :D

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 ?

Titlul: 023 Numere Prime
Scris de: Tatu Christian Alexandru din Octombrie 04, 2004, 23:12:23

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 :!:

Titlul: 023 Numere Prime
Scris de: Chris din Octombrie 08, 2004, 16:40:41

:roll: 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!!!

Titlul: ba nu
Scris de: vladut.forum din Iulie 11, 2005, 02:27:13

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 ;)

Titlul: 023 Numere Prime
Scris de: Dobre Catalin Andrei din Iulie 11, 2005, 09:36:23

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 )...

Titlul: 023 Numere Prime
Scris de: andreit1 din Iulie 11, 2005, 19:26:05

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

Titlul: 023 Numere Prime
Scris de: Deac Andrei din Septembrie 05, 2005, 17:38:34

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. [-o<

Titlul: 023 Numere Prime
Scris de: Filip Cristian Buruiana din Septembrie 05, 2005, 22:11:04

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);

Titlul: 023 Numere Prime
Scris de: Deac Andrei din Septembrie 06, 2005, 07:51:47

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)

Titlul: 023 Numere Prime
Scris de: Filip Cristian Buruiana din Septembrie 06, 2005, 10:36:36

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...

Titlul: 023 Numere Prime
Scris de: Adriana Sperlea din Septembrie 29, 2005, 19:17:08

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... :mrgreen:

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:31:25