023 Numere Prime

[•peanutz]

A, scuze, m-am uitat mai demult peste el.. oricum sintaxa e aceeasi, aproape...

[•Ramona2007]

am lucrat cu long long pe ideea k+1 la patrat si iau 80 puncte...poate daca aflu acel k+1 cu eratostene iau mai mult...acu imi iese din timp la ultimele 2 teste...asta e...

[•devilkind]

incearca sa mai optimizezi ciurul lui eratostene. Gasesti aici multe idei de optimizare http://infoarena.ro/Ciurul-lui-Erathostene

[•BigMazilu]

Test     Timp executie     Memorie folosita     Mesaj    Punctaj/test
1   4ms                 12kb         Ok!                           10
2   0ms                 8kb          Ok!                         10
3   1048ms              356kb   Time limit exceeded.   0
4   1048ms              356kb   Time limit exceeded.   0
5   1052ms              360kb   Time limit exceeded.   0
6   1052ms              360kb   Time limit exceeded.   0
7   1056ms              360kb   Time limit exceeded.   0
8   1052ms              356kb   Time limit exceeded.   0
9   1052ms              364kb   Time limit exceeded.   0
10   1048ms             360kb        Time limit exceeded.    0
Punctaj total                                                                    20



Ce o fi gresit??? Nu inteleg... Mai bine spus..care ar putea fi greseala uitandu-va peste rezultate..
CE INSEAMNA MEMORIE FOLOSITA??

[•stef2n]

Mesajul primit de la evaluator este destul de clar: programul tau ruleaza mai mult decat limita de timp impusa, iar coloana cu "Memoria folosita" exprima dimensiunea totala a variabilelor declarate de programul tau. Ca sa faci sa-ti intre problema in limita de timp, citeste toate cele 3 pagini ale topicului asta.

[•sima_cotizo]

Incearca sa citesti http://infoarena.ro/documentatie/borderoul-de-evaluare , iti va explica mai bine mesajele folosite destul de des de evaluatorarele de peste tot!

[•wefgef]

Gandeste mai mult, posteaza mai putin! 

Citeste paginile topicului inainte sa postezi! Raspunsul se afla intr-un post anterior.

[•c_e_manu]

Ai f multe indicatii despre cum ar trebui sa faci sa fie mai eficient... nu are rost sa repet...daca vrei insa neaparat explicatia de la A la Z trimite-mi un PM...

[•wefgef]

Mai incet cu scandalu...

Ia uite ce a postat nivan pe prima pagina a topicului:

eu am facut cu ciurul lui eratostene shi pe testele de la 6 la 10 imi da wrong answer. eu pracyic fac cu prim(k+1)^2

De aici eu trag concluzia ca poti afisa al k+1-lea numar prim la patrat. Hmm... ce chestie.


Dupa ore intregi de navigat... ajung intamplator pe a doua pagina a topicului... Mi-a luat o gramada de timp, dar am reusit!!! Ia uite ce gasesc aici:

p_100000= 1318699
http://ftp://ftp.externet.hu/pub/mirror/sac/educult/prime12.zip
aici e lista primelor 100.000 nr prime.
puteti are in jur de 800k.
daca e posibil puteti sa o folositi...in sursa cu ceva precompilat dar...
bineinteles nu ar fi nici pe departe o rezolvare ortodoxa.

Al 100.000-lea numar prim este 1318699... Si mi se mai da si un link de unde sa downloadez primele 100.000 de numere prime...

Mi-au trebuit o multime de calitati sa fac ce am facut... Sa stiu sa citesc in limba romana 

[•rEbyTer]

Dandu-se un numar K, afla cel mai mic numar N care nu este divisibil cu primele K numele prime, dar nu este prim.

Numerele care nu sunt divisibile cu 2, 3 sau 5 sunt : 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 49, .. 49 este cel mai mic numar care nu este prim.

Numerele sunt divisibile .

OMG ... de la 20pct am trecut la 100.. :/ .. pur şi simplu nu ştiam ce vroia' să zica (k+1)^2 .. de unde formula? măcar aşa de curiozitate ...

Câteva indicii pentru cei care nu au rezolvat încă problema...

1. cu ajutorul ciurului lui Eratostene am calculat primele 5.000.000 numere prime
2. am afisat numarul (k+1)^2
3. restu' s-a mai discutat şi nua re rost să mai repet

[•pauldb]

E mai bine sa dai sfaturi atunci cand sunt cerute. Daca la fiecare problema ar fi postata rezolvarea pe forum de cineva care a facut-o, nu ar mai fi asa de interesant site-ul, nu?

Cat despre formula, e destul de clar de ce e asa. Gandeste-te un pic.

[•rEbyTer]

păi ... pentru exemplul al doilea (k=3)

primele 3 nr prime sunt 2 3 5 ... rezultă că 7 (adică k+1) nu este divizibil cu 2 3 sau 5. dacă îl înmulţesc cu el însuşi nu mai este un număr prim dar îşi păstrează condiţiile care le-am zis mai inainte (nu e divizibil cu 2 3 5)

cred că asta e

[•valentinrosca]

Editat de admin: Invata sa vorbesti inainte sa intri pe forum!

[•valentinrosca]

Care este algoritmul? 

[•amadaeus]

Poate ca ar trebui sa citesti o parte din discutiile de pe acest thread. Cu siguranta iti vei forma o idee destul de clara asupra algoritmului...

[•valentinrosca]

Eu am observat ca n =(2k+1)^2...
 [-XSa nu faceti asa ca va da 10 puncte.
 :-kEu am facut asa:

Cod:

#include<fstream.h>
#include<math.h>
int long n,k,c,ok,b;
int main()
{
ifstream input("prim.in");
ofstream output("prim.out");
input>>k;
int np;
n=1;
np=0;
do
{
	n++;
    ok=1;
    for(c=2;c<=sqrt(n);c++)
		if(n%c==0)
			ok=0;
		if(ok)
			np++;
}
while(np<=k);
b=n*n;
output<<b;
return 0;
}

Mi-a dat 50 de puncte.
Dar care este algoritmul?

[•wefgef]

Trebuie sa rezolvi problema folosind ciurul lui Eratostene. Citeste posturile anterioare si sigur vei gasi indicii care sa te ajute! 

[•luigi]

deci am rezolvat problema cu ciuru dupa aia am facut inmultirea cu vect dar la ultimele 3 teste timpu trece.i cumva din cauza ca folosesc freepascal??
altceva nu vad ca ar putea fi...

[•CezarMocan]

Nu ai nevoie de inmultire pe numere mari. Rezultatul intra in int64.

[•luigi]

Merc mult...

[•Ionescu_Maria]

Se poate lua 100 de puncte fara Ciurul lui Erathostene? Eu am incercat fara: o data cu numere mari si am luat 80 de puncte,apoi cu long long si am luat 70. Greseala e mereu la timp. Nu ar fi trebuit sa iau mai putin cu nr mari si timpul sa fie mai mare?

[•c_e_manu]

Banuiesc ca ai folosit algoritmul brut... ceea ce am incercat si eu prima data si era in O(N^2). Operatiile cu numere mari sunt din cate stiu in O(N)... asa ca e posibil sa iei acelasi punctaj sau in cazul tau chiar mai bun. Eu as zice sa incerci si rezolvarea cu ciurul... E scurt, eficient si inveti cv nou!

[•xtreme]

Rezultatul cerut e mai mic ca si 2000000?

[•Mishu91]

Rezultatul cerut se incadreaza in Long Long

[•catalin93]

fii atent sa faci ciurul pana la 1.500.000 intrucat cel de-al 100.000-lea nr prim e undeva la 1.300.000
si restul intra in long long (n-ul)
bafta