infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Martie 08, 2004, 20:05:34



Titlul: 023 Numere Prime
Scris de: Dan-Leonard Crestez din Martie 08, 2004, 20:05:34
Aici puteţi discuta despre problema Numere Prime (http://infoarena.ro/problema/prim).


Titlul: 023 Numere Prime
Scris de: Andrei Grigorean din Iunie 15, 2005, 17:27:18
pe calcu meu imi merge in 1.49 secunde ptr k=100.000... chiar nu inteleg cum iau TLE pe 6 teste :-k


Titlul: 023 Numere Prime
Scris de: Andrei Grigorean din Iunie 29, 2005, 18:13:15
pe urmatoarea sursa iau 0 puncte (of course), dar imi da TLE pe 6 teste:
Cod:
var f:text;
    n,i:longint;

begin
  assign(f,'prim.in');reset(f);
    read(f,n);
  close(f);
  assign(f,'prim.out');rewrite(f);
    for i:=1 to n do ;
  close(f);
end.


ma poate ajuta cineva? si mai sunt in arhiva probleme unde patesc la fel.


Titlul: 023 Numere Prime
Scris de: Bunau Florin din Iulie 05, 2005, 16:05:41
Incearca ca la

Citat
for i:=1 to n do ;


sa pui in loc de ; instructiune vida sa pui o instructiune simpla.  :) cred #-o,  nu am testat vezi daca functioneaza...daca nu incearca in C/C++.
Daca inca nu jtii...ar fi bine sa te apuci :wink:


Titlul: 023 Numere Prime
Scris de: Andrei Grigorean din Iulie 05, 2005, 18:41:12
nevermind.. am invatat c++ si am facut unele programe si am luat in loc de 20 sau de 30 de puncte 100.

am mai descoperit k pot citi numerele caracter cu caracter si sa le transform. deasemenea am luat 100 pe cateva probleme.

totusi... ptr cei care lucreaza in pascal - dak cititi longinturi si primiti TLE desi algoritmul vostru ar trebui sa se incadreze in timp, sa stiti k nu e vina voastra. incercati una din alternativele pe care le-am descris mai sus.


Titlul: 023 Numere Prime
Scris de: Rus Cristian din Iulie 23, 2005, 07:33:53
asta cum se rezolva? :oops:


Titlul: 023 Numere Prime
Scris de: Filip Cristian Buruiana din Iulie 23, 2005, 09:09:20
Cu Ciurul lui Eratostenes. Si nu mai puneti intrebari de genul "CUM SE REZOLVA?", incercati singuri sa va dati seama... Daca am sti rezolvarile la toate problemele nu ar mai fi interesant...

  bubbleSORT


Titlul: 023 Numere Prime
Scris de: nivan din Noiembrie 08, 2005, 18:12:28
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


Titlul: 023 Numere Prime
Scris de: Rus Cristian din Noiembrie 08, 2005, 21:18:45
si eu am facut la fel, dar vezi ca s-ar putea ca numerele gasite...dupa ce le ridici la patrat, sa nu se mai incadreze in 2 miliarde, si poate de aia iti da WA...eu acolo am gresit, si dupa ce am corectat, am luat 100... :-'


Titlul: 023 Numere Prime
Scris de: nivan din Noiembrie 09, 2005, 19:54:02
teorteic asa ar fi   :oops:   doar ca am citit mai sus pe forum ca merge shi pe long long shi am crezut  \:D/  dar pe viitor nu mai bag mana in foc asa... cred ca totusi o sa fac o inmultire vector cu scalar.

Edit: Mei.... Merge pe long long  :yahoo:  doar k mie nu imi intra in timp, pe ultimele doua teste.

[Editat de bogdan2412: Asa cum am mai zis nu mai posta de doua ori consecutiv. Pentru asta e butonul de edit]


Titlul: testul 9
Scris de: Johny Deep din Decembrie 05, 2005, 07:18:02
Buna tuturor!

  Programul meu merge in o.01s (f. rapid), dar
la testul 9 iau WA. Va rog daca se poate sa-mi
scrieti care este numarul de la testul 9 (numai
fisierul .in ar fi suficient) pentru a putea sa-l
corectez.

 O zi buna !


Titlul: 023 Numere Prime
Scris de: Adriana Sperlea din Decembrie 05, 2005, 18:47:26
daca faci ciurul corect n-ar avea de ce sa nu mearga...poate doar daca ai lucrat pe numere mari (desi nu era nevoie, intra in long long) sa ai acolo o greseala...

EDIT: am observat ca sunt doua topicuri pentru problema asta in schimb nu e nici unul pentru problema perle. De ce?  :?:


Titlul: 023 Numere Prime
Scris de: Bogdan-Cristian Tataroiu din Decembrie 05, 2005, 19:27:18
Asta era topic pt Perle, dar cineva i-a schimbat numele  :?  Aparea ca "022 Numere Prime" in loc de "022 Perle" si a fost confundat... o mica greseala :mrgreen: Am inchis celalalt topic despre Numere Prime...

PS: De ce forumurile phpBB au optiune de Split pentru Topicuri dar n-au si Merge?  :annoyed:  :bored:


Titlul: cum ramane cu testul 9?
Scris de: Johny Deep din Decembrie 06, 2005, 12:54:44
Ma poate ajuta cineva ?
Intrebarea mea era pt. testul 9;
Nu am facut cu ciurul lui Eratostene!!


Titlul: 023 Numere Prime
Scris de: Bogdan-Cristian Tataroiu din Decembrie 06, 2005, 13:42:09
Politica siteului este de a nu face publice testele... Nu te astepta sa primesti un test.


Titlul: Re: cum ramane cu testul 9?
Scris de: Adriana Sperlea din Decembrie 06, 2005, 19:52:57
Citat din mesajul lui: johny
Ma poate ajuta cineva ?
Intrebarea mea era pt. testul 9;
Nu am facut cu ciurul lui Eratostene!!


Daca nu ai facut cu ciurul lui Eratostene spune-ne cum ai facut, poate asa o sa te ajute cineva. Ar fi mai constructiv decat sa ceri teste care daca te-ai fi uitat mai cu atentie pe forum ai fi observat ca nu se dau  [-X


Titlul: 023 Numere Prime
Scris de: u-92 din Decembrie 06, 2005, 20:09:40
la problema asta k <= 100.000.. deci poti sa faci usor un brute force sa vezi cat iti da pt fiecare numar


Titlul: 023 Numere Prime
Scris de: Sima Mihai Cotizo -vechi din Decembrie 30, 2005, 11:15:58
ok, folosit ciurul lui eratostene... done; folosit longint, longword, int64, qword... done (si imi da 50 puncte); folosit inmultire pe numere mari... done (si imi da 90 de puncte). iau WA la ultimu test  :cry:  poate explica cineva de ce?

[later edit]
gata, am gasit eroarea, era implementat bine, doar o limita a unui vector era cam mica...  :yahoo:


Titlul: 023Numere prime
Scris de: Iacob Ioan Fanica din Ianuarie 14, 2006, 20:51:29
Am folosit ciurul lui Eratostene, si am facut inmultirea pe numerele mari. Totul e bine pana la testul 8 cand imi da WA. De ce nuj ca ma incadrez in timp. Ar putea sa ma ajute cineva?


Titlul: 023 Numere Prime
Scris de: Adriana Sperlea din Ianuarie 15, 2006, 14:15:39
vezi sa nu ai o greseala la inmultirea pe numere mari. Mai bine foloseste long  long sau int64. verifica si limitele la vectori si detalii din astea.


Titlul: 023 Numere Prime
Scris de: Iacob Ioan Fanica din Ianuarie 19, 2006, 00:04:46
Inmultirea pe numerele mari e buna, iar limitele sunt cele din datele problemei. Am facut programul fara ciurul lui eratostene si am luat 80pct pe cand cu ciurul numai 70. De ce nuj.Am sa mai verific o data inmultirea pe numerele mari ca sa fiu sigur ca e corecta. :idea:

Nu mai conteaza. Pana la urma am luat 100 :yahoo:.
Greseala nu era implementarea pe numere mari ci tipul folosit la declararea variabilelor. Eu folosit unsigned long int si cred ca a intializat vectorul folosit la inmultirea pe numere mari cu alte valori si de aia WA la ultimele 3 teste. Acu folosit long long si merge => 100 puncte.
Mersi oricum de ajutor. :bye:  :mrgreen:


Titlul: 023 Numere Prime
Scris de: Xabre din Martie 14, 2006, 19:26:51
Ce parametru trebuie sa aiba fprintf ca sa poata afisa date de tipul long long?   :?


Titlul: 023 Numere Prime
Scris de: u-92 din Martie 14, 2006, 19:57:13
eu folosesc %lld


Titlul: 023 Numere Prime
Scris de: Xabre din Martie 15, 2006, 17:02:11
ciurul lui erathostene, long long ----  numa 50p....stiti cumva de ce?  :|
sa incerc cu numere mari? de la t 6 la 10 imi da WA


Titlul: 023 Numere Prime
Scris de: Andrei Grigorean din Martie 15, 2006, 22:10:10
fa pe numere mari si sigur merge ;)


Titlul: 023 Numere Prime
Scris de: andreit1 din Martie 15, 2006, 22:52:31
Ai grija la atribuiri de genul x=y*y unde x este long long si y este long pentru ca s-ar putea sa nu mearga. Asta bineinteles daca esti sigur ca nu ai gresit nimic altceva.


Titlul: 023 Numere Prime
Scris de: Bogdan-Cristian Tataroiu din Martie 16, 2006, 09:42:19
Citat din mesajul lui: wefgef
fa pe numere mari si sigur merge ;)


Sau ati putea sa nu va mai pierdeti timpul cu numere mari si sa va debugati programu :? E o singura operatie de inmultire care trebuie facuta pe long long si nu vad absolut nici o logica pentru care ati face pe numre mari... Al 100.000-lea numar prim e in jurul valorii de 1.000.000 din cate tin minte...

In cazul in care greseala este cea care a sugerat-o andreit1 (si e o posibilitate foarte mare ca asta sa fie avand in vedere ca ai WA doar pe testele 6-10 :) ) trebuie sa faceti o simpla conversie ca sa-ti mearga programu: x = (long long)y * (long long)y sau x = (long long)y * y...
Sfat: Nu cereti ajutor pe forum imediat ce nu luati 100 puncte... Testati-va programu pe teste mari... Daca greseala ta era la conversia asta atunci daca dadeai testu 100.000 observai ca-ti da un numar negativ sau 0 sau un numar cu mult prea putine cifre...


Titlul: 023 Numere Prime
Scris de: Xabre din Martie 17, 2006, 17:28:09
mersi ...asta era problema_>am luat 100p. :yahoo:
 N-am putut testa pe numere mari, ca am Borland C++ 4.02  si nu pot declara variabile de tip long long si nici siruri de peste 32000.   :|


Titlul: 023 Numere Prime
Scris de: Marius Stroe din Martie 17, 2006, 20:21:04
Citat
N-am putut testa pe numere mari, ca am Borland C++ 4.02 si nu pot declara variabile de tip long long si nici siruri de peste 32000. Neutral

Poate te ajuta http://info.devnet.ro/articole.php?page=art&art=87 ! :)


Titlul: 023 Numere Prime
Scris de: spx4 din Martie 19, 2006, 22:36:38
p_100000= 1318699
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.


Titlul: Raspuns: 023 Numere Prime
Scris de: Nicodei Eduard din Februarie 19, 2007, 10:40:25
mie mi-a mers foarte frumusel problema, folosind the ciur, pe un vector de tip bool cu 1500000 elemente, dak foloseam 1000000 primeam 50 pct. Si mai klumea a fost k n-am folosit inmultirea pe vectori: cand ajungeam la numarul cerut il afisam cu f2<<i*i; unde f2 era ofstream f2("prim.out"); si "i" era numarul al cariu patrat trebuia afisat. asta a fost tot.  :ok:


Titlul: Raspuns: 023 Numere Prime
Scris de: Florian Marcu din Februarie 22, 2007, 20:58:52
deci....m`am uitat pe ambele pagini la numere prime.....am incercat sa respect toate sfaturile...am facut ciurul lui eratostene corect...dar numai 50 de puncte.... ](*,)...dar tot iau TLE pe ultimile 5 teste...oare de ce...?  :? yo`s incepator....si as vrea sa ma ajute cineva...dak vrea..please...:D


Titlul: Raspuns: 023 Numere Prime
Scris de: Iacob Eduard din Februarie 23, 2007, 18:38:29
Stau de nush cate zile la probl asta,si tot nush ce am gresit.Iau 20 de punct.Am implementat corect ciurul.Ca sa fiu sigur ca nu am gresit la atribuiri,am declarat toate variabilele long long(in afara de vectorul pe care aplic ciurul,asta l-am facut bool).Nu pot sa aplic testele pe numere mari,ca nush cum sa fac in gnu c++ sa pot aloca un vector de 1400000 de elemente(al 101000 nr prim nu depaseste aceasta limita).Poate cineva macar sa imi arate cum pot sa fac asta,ca pe urma vad eu ce gresesc? ](*,)


Titlul: Raspuns: 023 Numere Prime
Scris de: Bondane Cosmin din Februarie 23, 2007, 19:15:03
Nu ai nevoie de numere mari, merge in long long.


Titlul: Raspuns: 023 Numere Prime
Scris de: Iacob Eduard din Februarie 23, 2007, 19:36:04
Nu am zis ca nu imi "intra" in long long ,ci ca nu merge sa aloc un vector cu 1400000 de elemente(necesare pt a implementa ciurul)


Titlul: Raspuns: 023 Numere Prime
Scris de: Airinei Adrian din Februarie 23, 2007, 20:11:41
Da putine detalii, eventual pune un cod sursa cu felul in care ai incercat sa declari un astfel de vector si nu a mers.. E destul de dubios ce spui tu, daca nu ai setat manual vreo limita la memorie nu vad de ce nu ar merge.


Titlul: Raspuns: 023 Numere Prime
Scris de: Iacob Eduard din Februarie 23, 2007, 20:46:18
Cod:
#include<fstream>
#define MarimeVector 1400000
using namespace std;

ifstream fin("prim.in");
ofstream fout("prim.out");

int main()
{
long long K,rezultat;
fin>>K;K++;

bool NumerePrime[MarimeVector];
for(long long i=2;i<MarimeVector;i++)
    NumerePrime[i]=1;
/...
}
Asta e sursa
[LE]Am incercat sa rulez executabilul,si sa introduc eu manual un numar K.Imi zice Sigsegv,Stack Fault... :sad:


Titlul: Raspuns: 023 Numere Prime
Scris de: Filip Cristian Buruiana din Februarie 23, 2007, 20:54:31
Incearca sa declari global
Cod:
bool NumerePrime[MarimeVector];


Titlul: Raspuns: 023 Numere Prime
Scris de: Iacob Eduard din Februarie 23, 2007, 20:59:23
In sfarsit imi merge si mie...Variabilele locale sunt alocate in stiva,asa ca de asta primeam mesajul de eroare.Credeam ca si in stiva poti sa aloci asa mult.Multumesc mult


Titlul: Raspuns: 023 Numere Prime
Scris de: Savin Tiberiu din Februarie 23, 2007, 21:21:16
stiva e de 1 MB. Atunci cand iti calculezi memoria e bine sa faci 2 calcule separate - unul ptr memoria globala si unul ptr stiva. De asemenea e bine sa eviti situatii la limita gen 1000kb de memorie in stiva.


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Martie 21, 2007, 19:01:38
Deci...vectorul trebuie sa fie de aprox. 1300000 elemente si probabil ca Borland C++ va da eroare sau un raspuns gresit, dar pe infoarena va da Ok! Cel putin asa s-a intamplat la mine. Succes!  :peacefingers:


Titlul: Răspuns: 023 Numere Prime
Scris de: Bondane Cosmin din Martie 21, 2007, 19:02:30
In borland c++ nu dispui de atata memorie :)


Titlul: Răspuns: 023 Numere Prime
Scris de: Valentin Stanciu din Martie 21, 2007, 19:09:10
Nu mai folositi borlandC!!

http://infoarena.ro/DJGPP-instalarea-de-la-A-la-Z


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Martie 21, 2007, 23:01:53
Citat
Nu mai folositi borlandC!!

http://infoarena.ro/DJGPP-instalarea-de-la-A-la-Z

Ms! Dar puteai sa zici mai devreme :P


Titlul: Răspuns: 023 Numere Prime
Scris de: Cezar Mocan din Martie 22, 2007, 08:30:57
Sau puteai tu sa cauti mai devreme prin site, ca sigur gaseai.


Titlul: Răspuns: 023 Numere Prime
Scris de: florea cristian din Aprilie 26, 2007, 13:07:26
Cine ma poate ajuta si pe mine sa imi explice putin ciurul lui eratostene?.....sau daca stiti vreun link va rog sa imi dati si mie


Titlul: Răspuns: 023 Numere Prime
Scris de: Bondane Cosmin din Aprilie 26, 2007, 13:17:53
http://infoarena.ro/Ciurul-lui-Erathostene


Titlul: Răspuns: 023 Numere Prime
Scris de: florea cristian din Aprilie 26, 2007, 13:23:12
ms cos-min...dar un link cu ciurul lui erathostene in pascal nu ai?


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Homorodean din Aprilie 26, 2007, 13:49:35
Incearca sa intelegi c, vei da des peste surse scrise in c.. Cel putin primele 2-3 variante ale ciurului nu au nimic de neinteles.. La ultimele e bine sa stii ca "<<" si ">>" sunt operatii pe biti care exista si in pascal shr, shl(parca)..


Titlul: Răspuns: 023 Numere Prime
Scris de: Silviu-Ionut Ganceanu din Aprilie 26, 2007, 21:53:04
Incearca sa intelegi c, vei da des peste surse scrise in c.. Cel putin primele 2-3 variante ale ciurului nu au nimic de neinteles.. La ultimele e bine sa stii ca "<<" si ">>" sunt operatii pe biti care exista si in pascal shr, shl(parca)..

Just a by the way: codul din articol e in Java  :-'


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Homorodean din Aprilie 26, 2007, 22:00:57
A, scuze, m-am uitat mai demult peste el.. oricum sintaxa e aceeasi, aproape...


Titlul: Răspuns: 023 Numere Prime
Scris de: Furtuna Ramona Cristina din Mai 28, 2007, 08:45:23
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...


Titlul: Răspuns: 023 Numere Prime
Scris de: Savin Tiberiu din Mai 28, 2007, 09:10:20
incearca sa mai optimizezi ciurul lui eratostene. Gasesti aici multe idei de optimizare http://infoarena.ro/Ciurul-lui-Erathostene


Titlul: Răspuns: 023 Numere Prime
Scris de: Mazilu Victor din Ianuarie 05, 2008, 17:07:47
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?????


Titlul: Răspuns: 023 Numere Prime
Scris de: Stefan Istrate din Ianuarie 05, 2008, 17:24:50
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.


Titlul: Răspuns: 023 Numere Prime
Scris de: Sima Cotizo din Ianuarie 05, 2008, 18:20:47
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!


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Grigorean din Aprilie 02, 2008, 16:55:37
Gandeste mai mult, posteaza mai putin!  [-X

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


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Aprilie 02, 2008, 21:26:42
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... :peacefingers:


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Grigorean din Aprilie 02, 2008, 21:31:40
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
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  :shock:


Titlul: Răspuns: 023 Numere Prime
Scris de: Herpesius din Aprilie 05, 2008, 18:38:23
Citat
Dandu-se un numar K, afla cel mai mic numar N care nu este divisibil cu primele K numele prime, dar nu este prim.

Citat
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 (http://dexonline.ro/search.php?cuv=divisibil) :P.

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


Titlul: Răspuns: 023 Numere Prime
Scris de: Paul-Dan Baltescu din Aprilie 05, 2008, 21:58:41
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.


Titlul: Răspuns: 023 Numere Prime
Scris de: Herpesius din Aprilie 06, 2008, 08:50:21
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


Titlul: Răspuns: 023 Numere Prime
Scris de: Rosca Valentin din Aprilie 22, 2008, 20:47:03
Editat de admin: Invata sa vorbesti inainte sa intri pe forum!


Titlul: Răspuns: 023 Numere Prime
Scris de: Rosca Valentin din Aprilie 22, 2008, 20:53:37
Care este algoritmul?  #-o


Titlul: Răspuns: 023 Numere Prime
Scris de: Lucian Boca din Aprilie 22, 2008, 20:58:09
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... ;)


Titlul: Răspuns: 023 Numere Prime
Scris de: Rosca Valentin din Aprilie 23, 2008, 15:53:47
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? #-o :-k


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Grigorean din Aprilie 23, 2008, 16:04:08
Trebuie sa rezolvi problema folosind ciurul lui Eratostene. Citeste posturile anterioare si sigur vei gasi indicii care sa te ajute!  :thumbup:


Titlul: /
Scris de: Pacala din Aprilie 30, 2008, 14:11:01
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...


Titlul: Răspuns: 023 Numere Prime
Scris de: Cezar Mocan din Aprilie 30, 2008, 14:21:17
Nu ai nevoie de inmultire pe numere mari. Rezultatul intra in int64.


Titlul: Răspuns: 023 Numere Prime
Scris de: Pacala din Mai 01, 2008, 10:08:40
Merc mult... :peacefingers:


Titlul: Răspuns: 023 Numere Prime
Scris de: Ionescu Maria-Dorina din Iulie 09, 2008, 19:39:47
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?


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Iulie 09, 2008, 21:12:02
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! :ok: :peacefingers:


Titlul: Răspuns: 023 Numere Prime
Scris de: speedzeal din Decembrie 28, 2008, 22:27:29
Rezultatul cerut e mai mic ca si 2000000?


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Misarca din Decembrie 28, 2008, 22:29:10
Rezultatul cerut se incadreaza in Long Long


Titlul: Răspuns: 023 Numere Prime
Scris de: Catalin Ionescu din Decembrie 28, 2008, 22:36:57
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 :)


Titlul: Răspuns: 023 Numere Prime
Scris de: speedzeal din Decembrie 28, 2008, 22:40:49
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 :)
am fakut ciurul de 2000000 nu pot sa inteleg ce nu merge...este n-u mai mare ca si 2000000?


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Misarca din Decembrie 28, 2008, 23:07:17
Eu am facut ciurul pana la 3 milioane, dar nu cred ca poate atinge mai mult de 2 milioane, dupa cum zicea in postul de mai sus


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Decembrie 28, 2008, 23:09:10
ai grija cum faci ciurul...mai cauta si alte greseli... insa daca faci corect 2 000 000 e mai mult decat suficient...


Titlul: Răspuns: 023 Numere Prime
Scris de: speedzeal din Decembrie 28, 2008, 23:11:05
cat ar trebui sa imi dea pentru k=100.000?
am fakut cu ciurul in 2 moduri diferite si tot 20 de puncte
Cod:
#include<iostream.h>    
#include<fstream.h>

int main()
    {
     unsigned char v[2000000];long int i,j,k,nrprime=0; 
     fstream f("prim.in",ios::in),g("prim.out",ios::out); 
     f>>k; 
     for(i=1;i<=2000000;i++) 
              v[i]='0'; 
     for(i=2;i<=2000000;i++) 
              if(v[i]=='0') 
                     { 
                     if(nrprime!=k) 
                            { 
                            nrprime++; 
                            for(j=i+i;j<=2000000;j+=i) 
                                       v[j]='2'; 
                            } 
                      else     
                             for(j=i+i;j<=2000000;j+=i) 
                                        if(v[j]=='0')   
                                               v[j]='1'; 
                      } 
     for(i=2;i<=2000000;i++) 
              if(v[i]=='1') 
                           {g<<i;break;} 
     f.close();g.close(); 
     return 0; 
     } 
[\code]       
                           
 


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Misarca din Decembrie 29, 2008, 00:05:22
De ce marchezi si cu 1 si cu 2?  :?


Titlul: Răspuns: 023 Numere Prime
Scris de: speedzeal din Decembrie 29, 2008, 00:08:36
De ce marchezi si cu 1 si cu 2?  :?
cu '0' nr prime cu '2' divizorii primelor k nr prime si cu '1' divizorii restu nr. prime


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Decembrie 29, 2008, 00:13:05
1689274677841 imi da mie...

http://infoarena.ro/job_detail/161860?action=view-source eu de obicei asa implementez ciurul... asa am facut si la problema asta si a mers... merge si cum ai facut tu... dar nu inteleg sensul sa marchezi si cu 2 ???

1689243484681 iti da cumva tie?


Titlul: Răspuns: Răspuns: 023 Numere Prime
Scris de: speedzeal din Decembrie 29, 2008, 00:31:31
1689274677841 imi da mie...

http://infoarena.ro/job_detail/161860?action=view-source eu de obicei asa implementez ciurul... asa am facut si la problema asta si a mers... merge si cum ai facut tu... dar nu inteleg sensul sa marchezi si cu 2 ???

1689243484681 iti da cumva tie?
nu imi da atat.....nu kred ka e buna ideea mea....eu am crezut ca daka marchez in vectoru de 2 milioane cu '0' nr prime si cu '2' divizori primelor k nr prime si cu '1' restu...e evident ca indicele care e cel mai mic si care in v de indice contine '1' acela e nr cautat
 


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Decembrie 29, 2008, 00:37:33
ai pe paginile astea un indiciu foarte important despre care este numarul cautat... e al (k+1)-lea numar prim la patrat.. credeam ca tu afisezi al k-lea numar prim la patrat... :D

asa problema se reduce sa faci ciurul si sa cauti al k-lea numar prim :)


Titlul: Răspuns: 023 Numere Prime
Scris de: speedzeal din Decembrie 29, 2008, 00:51:13
ai pe paginile astea un indiciu foarte important despre care este numarul cautat... e al (k+1)-lea numar prim la patrat.. credeam ca tu afisezi al k-lea numar prim la patrat... :D

asa problema se reduce sa faci ciurul si sa cauti al k-lea numar prim :)
.
mersi,mi-am dat seama atunci cand mi-ai zis rezultatul pentru k=100000


Titlul: Răspuns: 023 Numere Prime
Scris de: Catalin Ionescu din Decembrie 29, 2008, 01:39:58
De ce marchezi si cu 1 si cu 2?  :?
cu '0' nr prime cu '2' divizorii primelor k nr prime si cu '1' divizorii restu nr. prime

de ce nu iti faci un vector de bool si fiecare numar compus (neprim) il marchezi cu true... si astfel fiind initializat global pe false ai numere prime :)
mie asa mi se pare cel mai simplu :)


Titlul: Răspuns: 023 Numere Prime
Scris de: Vlad Schnakovszki din Ianuarie 14, 2009, 14:04:06
Imi puteti spune careva de ce iau Wrong answer pe ultimele 5 teste ? Am mai facut un program si al 100 000lea numar prim dadea undeva sub 1 300 000 deci aia e ok.

Cod:
#include <stdio.h>
#include <math.h>
long k, i, n=1300000, x;
bool v[1300000];
void prim(void)
{
for (i=3;i<=n;i=i+2)
v[i]=1;
for (i=3;i<=sqrt(n);i=i+2)
   for (register long t=i;t*i<=n;t++)
    v[i*t]=0;
}
int find(long k)
{
long t=1;
for (register int i=3;i<=n;i++)
if (v[i])
      {
    t++;
      if (t==k+1)
      return i;
      }
}
int main(void)   
{
freopen("prim.in", "r", stdin);
freopen("prim.out", "w", stdout);
scanf("%ld", &k);
prim();
x=find(k);
printf("%ld", x*x);
fcloseall();
return 0;
}

P.S.: E ceva in neregula cu declaratia long long int k, i, n=1300000, x; ? Ca daca incerc sa le declar asa imi spune Too many types in declaration.
La fel imi spune si daca nu mai scriu int, doar long long.


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Ianuarie 14, 2009, 17:00:37
Cod:
printf("%lld", x*x);

si declara-le long long... eu am declarat chiar unsigned long long pentru orice eventualitate, atunci cand am facut problema...


Titlul: Răspuns: 023 Numere Prime
Scris de: Pripoae Teodor Anton din Ianuarie 16, 2009, 20:11:09
La mine pe g++ 4.3 de linux, aproximativ la fel cu cel de pe infoarena care e 4.2.3, programul tau compileaza si cu long long. Tu compilezi cumva cu Borland? Borland-ul nu e standard, si nu accepta long long, de aceea crede probabil ca e o eroare la tine.


Titlul: Răspuns: 023 Numere Prime
Scris de: Vlad Schnakovszki din Ianuarie 18, 2009, 10:15:03
L-am trimis cu toate ca Borlandu zicea ca am eroare :) Am luat 100 de puncte, mersi :winner1:. Daca am ajuns sa nu mearga programu din cauza lui Borland inseamna ca am inghitit destul :-#. Care ziceti ca e cel mai bun editor/compilator ? Si eventual un link pentru el  :-k Thanks :D


Titlul: Răspuns: 023 Numere Prime
Scris de: Gabriel Bitis din Ianuarie 18, 2009, 12:59:54
http://infoarena.ro/schimbare-borland/pachet (http://infoarena.ro/schimbare-borland/pachet)


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Ianuarie 18, 2009, 19:20:05
eu votez cu rhide :-'
http://infoarena.ro/djgpp-instalarea-de-la-a-la-z


Titlul: Răspuns: 023 Numere Prime
Scris de: Pripoae Teodor Anton din Ianuarie 18, 2009, 22:01:50
@emanuel

DJGPP este mult mai vechi, deci si mai indepartat standardului decat MINGW. Nu de putine ori unele programe care compilau cu DJGPP nu compilau cu gcc pe linux, si invers, fapt care mergea cu MINGW. De asemenea, RHIDE, desi este mai asemanator Borland-ului, are mult mai multe buguri, si chiar sa intampla sa crape cu totul, fara sa iti salveze sursa, MINGW Studio sau Dev-Cpp nefacand asta.


Eu personal l-as sfatui pe Vlad sa foloseasca Code Blocks, un mediu de altfel folosit si testat cu succes de mine in ultimii aproximativ 2 ani, atat pe windows cat si pe linux, neavand absolut nici o problema cu el. Compilatorul poate fi setat individual, putand sa compileze chiar si cu Borland, iar editorul este foarte flexibil, poti schimba aproape orice la el, poti seta comenzi de compilare, de rulare, etc, lucruri care nu se pot face in MINGW Developer Studio.

Este alegerea ta ce vrei sa folosesti :)


Titlul: Răspuns: 023 Numere Prime
Scris de: Paul-Dan Baltescu din Ianuarie 19, 2009, 00:16:40
Incercati sa ramaneti la subiect. Sunt destule topicuri pe forum unde se discuta despre editoare/compilatoare.


Titlul: Răspuns: 023 Numere Prime
Scris de: Mihai-Alexandru Dusmanu din Februarie 05, 2009, 17:11:55
am incercat sa pregenerez primele 100000 de nr prime... dar nu pot sa trimit programul pentru ca are cam 670 KB si maximul admis e 256 :O...


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Februarie 05, 2009, 18:41:07
Citat
am incercat sa pregenerez primele 100000 de nr prime... dar nu pot sa trimit programul pentru ca are cam 670 KB si maximul admis e 256 :O...

nu merge fiindca nu se rezolva astfel... incearca sa-ti invingi lenea si citeste threadul acesta... :)


Titlul: Răspuns: 023 Numere Prime
Scris de: Vasile din Martie 09, 2009, 13:15:50
Pentru sursa de mai jos imi da la ultimele 5 teste : Killed by signal 11(SIGSEGV).
Unde este problema?
PS: am folosit numarul 1318699 pt ca este al 100 000 numar prim.
Cod:
#include <stdio.h>
char iprim [1318699];
int k;
long int x;
void citire ()
{
scanf("%d",&k);}
void prim (int k)
{
long int i,j;
int nr=0;
for(i=2;i<=1318699;i++)
    if(nr<k){
if(!iprim[i ]){
      x=i;
      ++nr;
      for(j=i*i;j<=1318699;j+=i)
iprim[j]=1;}}
else break;
}
int main ()
{
freopen ("prim.in", "r", stdin);
freopen ("prim.out", "w", stdout);
citire();
prim(k+1);
printf("%ld", x*x);
return 0;}

 Foloseste tag-ul [ code ] !


Titlul: Răspuns: 023 Numere Prime
Scris de: Paul-Dan Baltescu din Martie 09, 2009, 13:23:07
Rezultatul este de tip long long.

Nu mai posta cod ca sa-ti caute lumea greselile. Testeaza-ti singur.


Titlul: Răspuns: 023 Numere Prime
Scris de: Vasile din Martie 09, 2009, 17:14:09
Ok am inteles. Dar ma gandeam ca daca aflu acum care e greseala, pe viitor cand va aparea aceeasi eroare voi sti ce sa fac.
De testat... l-am testat mai mult timp decat l-am conceput... sunt unele greseli care nu ai cum sa le aflii singur. ;).
Am corectat acum si vad ca imi da aceeasi eroare, in fine voi incerca din nou sa vad daca pot sa rezolv.
Multumesc.


Titlul: Răspuns: 023 Numere Prime
Scris de: Andrei Grigorean din Martie 09, 2009, 17:35:43
Sunt 3 erori in sursa ta:

  • Vectorul tau trebuie declarat de marime 1318700, deoarece in C daca aloci un array de dimnesiune N poti accesa elemente cu indicii cuprinsi intre 0 si N-1.
  • Rezultatul afisat trebuie sa fie de tipul long long - poti sa faci un cast la printare: printf("%lld\n", ((long long)x) * x);
  • In forul in care marchezi multiplii unui numar prim nu trebuie sa incepi de la i*i deoarece aceasta valoare iese din int. E de ajuns sa pornesti de la i ;)


Titlul: Răspuns: 023 Numere Prime
Scris de: Vasile din Martie 10, 2009, 19:41:42
Multumesc. Am rezolvat.


Titlul: Răspuns: 023 Numere Prime
Scris de: Rosca Valentin din Aprilie 02, 2009, 14:29:36
Aici merge __int64 ???


Titlul: Răspuns: 023 Numere Prime
Scris de: Gabriel Bitis din Aprilie 02, 2009, 16:05:51
Nu. Foloseste long long in loc de __int64.


Titlul: Răspuns: 023 Numere Prime
Scris de: Rosca Valentin din Aprilie 03, 2009, 19:09:59
Mi-am dat seama. :D

Raspunsu este al k+1 numar prim la patrat.
I-mi iese 50 de puncte.
Nu-mi iese la numere mari.
Ma poate ajuta cineva la chestia asta.Va rog! [...]
Eu lucrez in C++.
[..]
Pls!
Va rog!
[...]

[editat de moderator] Nu mai posta consecutiv si fii sigur ca daca folosesti multe smiley-uri nu vei fi ajutat prompt!


Titlul: Răspuns: 023 Numere Prime
Scris de: Sima Cotizo din Aprilie 03, 2009, 19:15:47
Incearca sa faci debug sau fii mai exact cand spui ca nu-ti iese.


Titlul: Răspuns: 023 Numere Prime
Scris de: Vladimir Oltean din Aprilie 05, 2009, 21:42:22
ajutati-ma si pe mine, va rog frumos. am o problema foarte dubioasa. am facut problema, merge corect si pe testul cu 100.000, dar imi afiseaza gresit :fool:
stiu sigur ca algoritmul e bun, pentru ca in debug imi apare valoarea corecta, dar in fisierul de iesire e o aberatie. mai precis, am codul urmator:

Cod:
#include <stdio.h>
#define N 1318700

bool prim[N];
long long x;
int count,k;

int main()
{
freopen("prim.in","r",stdin);
freopen("prim.out","w",stdout);

scanf("%d",&k);
[...]
for(...)
if(...)
{ x=i*i;
printf("%lld",x);
break;
}
}
fclose(stdin); fclose(stdout);
return 0;
}

exact asta fac. e foarte dubios, pentru ca daca dau 100000, in debug imi arata x ca fiind 1.689.274.677.841, iar in fisierul de iesire, in urma instructiunii printf("%lld",x) imi afiseaza 1.352.530.513. ce gresesc? ??? ???


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Aprilie 05, 2009, 21:47:09
Folosesti cumva Borland? Eventual incearca si cu streamuri sau "%I64" (aici s-ar putea sa ma insel, ca nu am folosit niciodata :P) in loc de "%lld".


Titlul: Răspuns: 023 Numere Prime
Scris de: chisinau gheorghita din Aprilie 05, 2009, 21:47:31
vine "%I64d". Dar totusi pe infoarena trimie cu "%lld" pt ca se testeaza pe linux!


Titlul: Răspuns: 023 Numere Prime
Scris de: Vladimir Oltean din Aprilie 05, 2009, 21:50:04
 ??? am luat suta cu fstream. as fi recunoscator daca mi-ar explica cineva de ce.
nu folosesc borland, folosesc mingw studio. din cate am inteles ar trebui sa se comporte la fel cu compilatorul de pe infoarena.

[Edit]
foarte foarte aiurea... cu "%I64d" ala iau doar 50..

[Later edit]
eu nu mai inteleg absolut nimic.. deci cu fstream e ok si la mine si pe site, dar mi-e mie incomod. cu stdio imi da mie bine daca folosesc "%I64d", dar da gresit pe site. daca folosesc "%lld", imi da gresit pe compilatorul meu, dar corect in evaluator. e aiurea rau de tot :fool:


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Aprilie 05, 2009, 21:58:57
Pe MinGW e un mic bug despre care s-a mai vorbit pe infoarena la afisarea unui "long long" folosind printf(). Eu mai nou folosesc streamuri fiindca au devenit mai rapide. Doar in concursuri in care se folosesc compilatoare mai vechi folosesc printf() si scanf(). Plus ca imi e mai usor sa scriu un fout<<var decat printf("%d",var). :-'


Titlul: Răspuns: 023 Numere Prime
Scris de: Vladimir Oltean din Aprilie 05, 2009, 22:02:41
fout>>var

 :rotfl: :rotfl: semnele nu se pun invers (<<) din cate stiu eu? :P e clar cat iti e de usor...


Titlul: Răspuns: 023 Numere Prime
Scris de: Sima Cotizo din Aprilie 05, 2009, 22:04:12
[Later edit]
eu nu mai inteleg absolut nimic.. deci cu fstream e ok si la mine si pe site, dar mi-e mie incomod. cu stdio imi da mie bine daca folosesc "%I64d", dar da gresit pe site. daca folosesc "%lld", imi da gresit pe compilatorul meu, dar corect in evaluator. e aiurea rau de tot :fool:

Este o diferenta intre MinGW si g++ la afisarea numerelor long long. Pe g++ se foloseste %lld; pe MinGW, I64d. Cum pe infoarena se compileaza cu g++, iata de ce iei bine aici si gresit la tine cand afisezi cu lld.

Fstream se descurca la fel si pe MinGW si pe g++ si de-aia e ok in ambele parti.


Titlul: Răspuns: 023 Numere Prime
Scris de: Vladimir Oltean din Aprilie 05, 2009, 22:06:36
Este o diferenta intre MinGW si g++ la afisarea numerelor long long. Pe g++ se foloseste %lld; pe MinGW, I64d. Cum pe infoarena se compileaza cu g++, iata de ce iei bine aici si gresit la tine cand afisezi cu lld.

Fstream se descurca la fel si pe MinGW si pe g++ si de-aia e ok in ambele parti.

multumesc pentru clarificare :D asta inseamna ca e cazul sa-mi schimb compilatorul cu unul mai asemanator cu g++?


Titlul: Răspuns: 023 Numere Prime
Scris de: Emanuel Cinca din Aprilie 05, 2009, 22:06:50
fout>>var

 :rotfl: :rotfl: semnele nu se pun invers (<<) din cate stiu eu? :P e clar cat iti e de usor...

My bad  :P


Titlul: Răspuns: 023 Numere Prime
Scris de: Sima Cotizo din Aprilie 05, 2009, 22:21:27
multumesc pentru clarificare :D asta inseamna ca e cazul sa-mi schimb compilatorul cu unul mai asemanator cu g++?
Nu neaparat. Daca ai in vedere diferenta asta, atunci poti sa folosesti MinGW in continuare (care e foarte asemanator cu g++ oricum). Poti sa incerci si Visual Studio Express care mi se pare ca afiseaza tot cu lld...


Titlul: Răspuns: 023 Numere Prime
Scris de: Rosca Valentin din Aprilie 10, 2009, 10:37:03
Pai am facut un program de 90 pt si la ultmul test imi iese din timp
si nu stiu testul.Dar o sa rezolv chestia asta


Titlul: Răspuns: 023 Numere Prime
Scris de: A Cosmina - vechi din August 01, 2009, 12:17:41
Salut ! Am citit tot topicul si am gasit informatii folositoare legate de problema. :? Am incercat sa fac intocmai: pun intr-un vector x toate numerele prime pana la 5.000.000 apoi afisez  (x[K+1]*x[K+1]). Numai ca imi da 1, am facut afisare anumerelor din vector si este buna. Cred ca problema mea ar fi la ciur pentru ca afisarea am facut-o astfel:

Cod:
 for(int i=2;i<=max;i++) 
if(x[i]==1) std::cout<<i<<' ';

Asa ca am incercat

Cod:
(x[K+1+2])*(x[K+1+2])
pentru ca eu incep i-ul de la 2. Insa tot nu merge.

Unde ar putea fi problema?  :sad:


Titlul: Răspuns: 023 Numere Prime
Scris de: Codrea Marcel din August 01, 2009, 13:05:57
Din ce am inteles eu, tu in vectorul x ai ciurul si nu sirul de numere prime(ai si numere neprime acolo).
Tu prin (x[K+1]*x[K+1]) nu ridici la patrat al (K+1)-lea numar prim ci al (K+1)-lea numar.  Tu trebuie sa iterezi prin vectorul x si sa numeri cate de (x[it] == 1) ai (cate numere prime ai) cu o variabila aux, si doar cand aux pe care o numeri astfel, e egala cu k+1 trebuie sa afisezi x[it] * x[it] unde it e valoarea iteratorului.


Titlul: Răspuns: 023 Numere Prime
Scris de: A Cosmina - vechi din August 01, 2009, 19:11:31
Am descoperit ce greseam era la ciur ! Am reusit, mersi .  :)

Edit: Am observat niste gresel in enuntul problemei:

Citat
Demonstreaza ca ideea lui Ghoerghe este doar o aproximare. Dandu-se un numar K, afla cel mai mic numar N care nu este divizibil cu primele K numele prime, dar nu este prim.

Nu-i o observatie rautacioasa, vreau doar sa atrag atenita asupra acestor greseli minore.  :)


Titlul: Răspuns: 023 Numere Prime
Scris de: Paul-Dan Baltescu din August 01, 2009, 21:04:09
Am rezolvat. Este bine ca semnalati astfel de erori!  :thumbup:


Titlul: Răspuns: 023 Numere Prime
Scris de: Vlad Tarniceru din Decembrie 11, 2009, 19:30:04
salut tuturor.as avea o problema in legatura cu problema :? .la programul meu se blocheaza,am facut cu ciurul lui erastostene dar nu-mi merge(se blocheaza cand dau pe execute).ma poate ajuta cineva?va rog mult!!!uite sursa mea:
Cod:
#include<stdio.h>
 int a[10000],x[10000000],i,j,k,l=0,z,dk;
 int q=0;
 FILE *f,*g;
 int ciur(){
     for(i=1;i<=1000000;i++)
         a[i]=0;
     i=2;
     dk=k;
     while(i<=1000){
         if(a[i]==0)
             for(j=i+i;j<=1000000;j+=i)a[j]=1;
         i++;
     }
     j=1;
     for(i=1;dk>0;i++) if(a[i]==0) {dk--;x[j++]=i;}
 }
  int main(){
      f=freopen("prim.in","rt",stdin);
      g=freopen("prim.out","wt",stdout);
      printf("%d",k);
      ciur();
      q=2;
      while(l==0){
         z=1;
         while(a[q]==0) q++;
         while(q%x[z]==0 && z<=k) z++;
         l=(z==k);
         q++;
      }
      fprintf(g,"%d",q);
      fclose(g);
      return 0;
  }
daca isi da cineva seama unde e eroarea sa scrie pe forum sau pe id-ul meu vladtarniceru(sau sa mi-o trimita mail la [email protected]). :peacefingers:


Titlul: Răspuns: 023 Numere Prime
Scris de: Florian Marcu din Decembrie 11, 2009, 22:32:41
Tu nu citesti k-ul (  printf("%d",k); ). a[] e prea mic declarat. Fa si tu un debug ( cu watch, sau cu afisari ). Nu cred ca e indicat sa postezi pe forum chiar orice problema. In curand o sa discutam aici erori de compilare. Nu cred ca asta e scopul infoarena. Spor!  :thumbup:


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Ianuarie 21, 2010, 20:49:46
Deci nu pot sa cred de ce imi da la ciur aiurea: al 100.000-lea nr. prim zice ca e 1299709 :( ce am putut gresi? Ciurul l-am facut in 2 moduri si tot asa


Titlul: Răspuns: 023 Numere Prime
Scris de: Mihai Calancea din Ianuarie 21, 2010, 21:54:43
Pai..ala e. Probabil n-ai folosit long long pentru rezultat.


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Ianuarie 22, 2010, 14:07:20
Cod:
#define MAX 1500000
bool v[MAX];
long long p[MAX]
Crezi ca e gresit ?


Titlul: Răspuns: 023 Numere Prime
Scris de: Mihai Calancea din Ianuarie 22, 2010, 14:09:12
Nu am idee ce faci tu cu p-ul ala , rezultatul e long long int , asta spuneam.


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Ianuarie 22, 2010, 14:13:35
in p tin numerele prime, adica p1=3, p2=5 ..... si b rezultatul e long long


Titlul: Răspuns: 023 Numere Prime
Scris de: Paul-Dan Baltescu din Ianuarie 22, 2010, 15:24:35
M-am uitat pe codul tau si am observat ca faci o greseala frecventa. La un moment dat, faci b = p[k]*p[k], b fiind long long, iar vectorul p e un vector de numere intregi. In astfel de situatii, p[k]*p[k] este intai convertit la int (trunchiat) si apoi pus in numarul b. Daca vrei sa nu se trunchieze rezultatul, ai doua optiuni:

1. sa folosesti operatorul cast:
Cod:
b = (long long) p[k]*p[k];

2. sa introduci un termen de tip long long in produsul din dreapta, astfel incat sa nu se modifice rezultatul, adica:
Cod:
b = 1LL * p[k] * p[k];

1LL inseamna valoarea 1 de tip long long. (Daca inmultesti ceva cu 1, produsul nu se schimba.)

Ai grija ca greseli similare apar si la impartirea a doua numere. Daca faci a/b, iar a si b sunt intregi, rezultatul va fi egal cu catul impartirii; daca a sau b e de tip real, rezultatul va fi chiar valoarea fractiei.


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Ianuarie 22, 2010, 15:47:09
Merci Dan 100p  :winner1: dar totusi de ce imi da in program nr. prim al 100000-lea gresit ?


Titlul: Răspuns: 023 Numere Prime
Scris de: Paul-Dan Baltescu din Ianuarie 22, 2010, 15:54:41
Pai nu pare sa fie gresit. Cineva ti-a confirmat intr-un post mai devreme ca e bun. (Mihai Calancea)


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Ianuarie 22, 2010, 15:55:41
Dar de ce pe siteuri zice ca al 100.000-lea nr. prim e 131...... ?


Titlul: Răspuns: 023 Numere Prime
Scris de: Mihai Calancea din Ianuarie 22, 2010, 21:46:19
http://www.wolframalpha.com/input/?i=100000+th+prime
Poate ai citit gresit. Poti folosi wolframalpha pentru majoritatea chestiilor de genul  :) Joaca-te cu el si ai sa vezi.


Titlul: Răspuns: 023 Numere Prime
Scris de: Halalai Tudor Andrei din Februarie 23, 2010, 13:47:25
am trimis o sursa si-mi da
Citat
Killed by signal 8(SIGFPE).
ce-o mai fi si asta :??


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Februarie 23, 2010, 14:07:00
Cod:
8(SIGFPE): Floating point error. Cauzat cel mai frecvent de impartiri la 0.
Alta data cauta aici (http://infoarena.ro/documentatie/evaluator)


Titlul: Răspuns: 023 Numere Prime
Scris de: Vlad Tarniceru din Martie 13, 2010, 11:28:46
pai nu cumva numarul cautat este (al n+1-lea nr prim)^2?
de exemplu pt n=3 avem numerele 2,3,5 ,iar nr cautat este 49,adica 7*7(7 e urm numar prim dupa 5) ???


Titlul: Răspuns: 023 Numere Prime
Scris de: Florian Marcu din Martie 13, 2010, 15:45:19
pai nu cumva numarul cautat este (al n+1-lea nr prim)^2?
de exemplu pt n=3 avem numerele 2,3,5 ,iar nr cautat este 49,adica 7*7(7 e urm numar prim dupa 5) ???
Implementeaza si taci !   :)


Titlul: Răspuns: 023 Numere Prime
Scris de: Vlad Tarniceru din Martie 13, 2010, 15:50:18
bine dar iau 20 de puncte  :D si nu stiu de ce :readthis: .am pus unsigned long long si zice WA oare o fi de la ciur? :?


Titlul: Răspuns: 023 Numere Prime
Scris de: Vlad Tarniceru din Martie 14, 2010, 09:08:01
gata s-a rezolvat  :D .m-a ajutat robert simoiu multumesc inca o data  :D :winner1:


Titlul: Răspuns: 023 Numere Prime
Scris de: Alexandru-Iancu Caragicu din Decembrie 08, 2010, 19:47:00
Ar trebui spus numar > 1.


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Decembrie 08, 2010, 20:45:34
Ar trebui spus numar > 1.
Adica ?


Titlul: Răspuns: 023 Numere Prime
Scris de: Alexandru-Iancu Caragicu din Decembrie 08, 2010, 20:49:22

Adica raspunsul ar trebui sa fie intotdeauna 1.


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Decembrie 08, 2010, 20:52:12
Adica mai mare decat 1. Da .... e mai mare decat 1, logic.


Titlul: Răspuns: 023 Numere Prime
Scris de: FMI - Roscaneanu George din Martie 09, 2011, 22:51:58
 ](*,) Eu tot incerc dar tot timpul imi iese doar 50 puncte...
Folosesc ciurul si folosesc variabile in long long...
Ultimele 5 teste imi dau WA.

EDIT IMPORTANT
Spunetimi si mie va rog frumos....
1299721*1299721=1352530513 sau 1689274677841.
Mie mi se pare ca a doua e corecta dar compilatorul imi da 100 pentru prima...
Cum se poate ca ultima cifra (1) ridicata la patrat sa dea 3, si totusi imi da 100 de puncte..............


Titlul: Răspuns: 023 Numere Prime
Scris de: Usurelu Daniel Constantin din Martie 28, 2011, 15:37:15
Chiar asa de grea e .Incat sa iei 0 puncte :rotfl:



Titlul: Răspuns: 023 Numere Prime
Scris de: Alexandru Popescu din Aprilie 11, 2011, 10:26:21
De ce este timpul asa mare la problema asta?
Multi am scos sub 0.3.


Titlul: Răspuns: 023 Numere Prime
Scris de: Sorin Rita din Aprilie 11, 2011, 12:09:26
Si mie mi se par limitele exagerat de mari...si limita de timp si de memorie...mi se pare un pic ciudat ca am eliminat un for de la 1 pana la un milion jumate(in care mergeam din unu in unu) si totusi timpul de executie a scazut cu maxim 20ms.


Titlul: Răspuns: 023 Numere Prime
Scris de: UAIC.VlasCatalin din Iulie 06, 2011, 23:17:57
nu inteleg ce fel de compilator fpc e pe site, la mine programul merge pentru k=100 000  in 0.45 sec dar pe site iau TLE la ultimul test, iar penultimul merge in 620ms. Chiar nu inteleg si nu stiu ce pot sa mai optimizez.  Nu stie cineva ce e de facut?


Titlul: Răspuns: 023 Numere Prime
Scris de: Robert din Ianuarie 21, 2012, 20:26:48
E o greseala... 1 nu este numar prim. Deci la toate testele ar trebui sa afisezi 1.  :D


Titlul: Răspuns: 023 Numere Prime
Scris de: Jugarean Sergiu din Martie 02, 2012, 22:26:42
Am luat si eu in sfarsit 100 pct  =D&gt; . Folosit ciurul, afisat al k+1-lea numar prim la patrat si gata!


Titlul: Răspuns: 023 Numere Prime
Scris de: Carabian Ovidiu din Decembrie 24, 2012, 14:01:46
ce ii la testul 8 ca imi da TLE? ](*,)


Titlul: Răspuns: 023 Numere Prime
Scris de: Simoiu Robert din Decembrie 24, 2012, 14:19:42
Iti da TLE pentru ca algoritmul tau nu e eficient, trebuie folosit la problema asta Ciurul lui Eratosthenes (http://infoarena.ro/problema/ciur).


Titlul: Răspuns: 023 Numere Prime
Scris de: Tudorica Andrei din Ianuarie 11, 2013, 15:36:59
iau 3 TLE-uri... ce as mai putea optimiza? #-o


Titlul: Răspuns: 023 Numere Prime
Scris de: Visan Radu din Ianuarie 11, 2013, 15:54:03
Iei 100 daca faci:
Cod:
if(!prim[i])
        {
            nr++;
            if(nr == k + 1) return i;


Titlul: Răspuns: 023 Numere Prime
Scris de: Tudorica Andrei din Ianuarie 11, 2013, 22:16:55
Multumesc! :ok:


Titlul: Răspuns: 023 Numere Prime
Scris de: Ungurianu Alexandru din Martie 24, 2013, 13:29:41
Se poate uita cineva si peste sursa mea? Iau 70p pe ea, si din cate am reusit eu sa imi dau seama este ca imi sare niste numere prime de la 10000 in sus, si nu pot sa imi dau seama de ce.
http://www.infoarena.ro/job_detail/925090 (http://www.infoarena.ro/job_detail/925090)


Titlul: Răspuns: 023 Numere Prime
Scris de: Balescu Ovidiu-Gheorghe din Februarie 21, 2014, 13:12:43
Se poate uita cineva la sursa mea, scrisa mai jos? Imi da 50 de puncte fiindca la ultimele 5 teste imi iese din timp. Pana acum nu am reusit sa gasesc o solutie sa mearga mai repede.

Cod:
#include<stdio.h>
#include<stdlib.h>
unsigned long k,d,i,q=1,n=3,N; unsigned a[99988]; short flag=1;
int main()
{
    FILE*f=fopen("prim.in","rb"); fscanf(f,"%lu",&k); fclose(f);
    FILE*g=fopen("prim.out","wb");
    if(k>1)
    {
        while(q<k)
        {
            flag=0;
            for(d=3;d*d<=n&&!flag;d+=2)
                if(n%d==0) flag=1;
            if(flag==0)
            {
                q++;
                a[q]=n;
            }
            n+=2;
        }
        N=n;
        while(flag==0)
        {
            n+=2;
            for(d=N;d*d<=n&&!flag;d+=2) if(n%d==0) flag=1;
            if(flag==1) for(i=2;i<=k&&flag;i++) if(n%a[i]==0) flag=0;
        }
        fprintf(g,"%ld",n);
    }
    else fprintf(g,"%d",9);
    fclose(g);
    return 0;
}


Titlul: Răspuns: 023 Numere Prime
Scris de: Tudor Maxim din Septembrie 02, 2014, 22:57:29
pe ultimele 6 teste iau TLE...am neaparat nevie de optimizare pe biti la ciurul lui erastostene ca sa iua 100?


Titlul: Răspuns: 023 Numere Prime
Scris de: Mihai Calancea din Septembrie 02, 2014, 23:44:36
Nu, dar ce ai facut tu acolo nu e ciurul lui Eratosthene. Tu verifici primalitatea lui x in O(x).

http://www.infoarena.ro/problema/ciur

Ai aici detalii despre ciur  :)


Titlul: Răspuns: 023 Numere Prime
Scris de: andrei din Martie 01, 2015, 22:35:21
Am aici   :D o demonstratie facuta de mine pt. a sustine ca cel mai mic numar neprim nedivizibil prin primele k numere prime e al k+1 numar prim la patrat, nus daca e corecta ce ziceti?  :fool:


Titlul: Răspuns: 023 Numere Prime
Scris de: Vladianu Cosmin din Martie 01, 2015, 22:42:22
Da...ce mai demonstratie ai boss..e inversul verificarii daca un numar e prim.
E corect,trebuie afisat al k+1-lea numar prim,ceea ce poti observa din exempli,si daca nu te-ai convins mai iei cateva si observi ca asta-i :)


Titlul: Răspuns: 023 Numere Prime
Scris de: FMI Ciobanu Andrei din Septembrie 02, 2015, 12:23:26
Daca introduc valori in prim.in imi da raspunsul corect dar nu inteleg de ce cand il uploadez primesc 0 puncte deoarece toate raspunsurile sunt incorecte. Ma poate ajuta cineva?

Cod:
#define lim 1000000
#include <fstream>
using namespace std;

bool prim [lim];

fstream f("prim.in");
ofstream g("prim.out");

int main()
{
    int i,j,c=0,k;
f>>k;
for(i=2;i<lim;i++)
{
    if(prim[i]==0)
        {
            c++;
    for(j=i*2;j<=lim;j+=i)
       prim[j]=1;
       }
    if(prim[i]==0) if(c==k+1){ g << i*i; return 0;}
}
}


Titlul: Răspuns: 023 Numere Prime
Scris de: Slevoaca Stefan-Gabriel din Octombrie 24, 2015, 15:35:36
Am facut problema initial cu Erastotene si am alocat static un tablou de 1.500.000 de elemente (bool eras[1500000]) si primeam killed by signal 11 pe primele 2 teste si 80p.. apoi am alocat dinamic tabloul eras (bool *eras; eras = new bool[1500000];) si am luat 100p. Vreo idee de ce diferenta asta ?? o fi din cauza dimensiunii prea mari a tabloului ??


Titlul: Răspuns: 023 Numere Prime
Scris de: Dinu Cristian din Martie 30, 2016, 08:15:50
Am observat ca evaluatorul nu accepta din cstdio (cand folosesc fscanf si fprintf) I64d, am luat incorect pe teste si am schimbat in %lld si a dat bine


Titlul: Răspuns: 023 Numere Prime
Scris de: Daniel Rusu din Ianuarie 05, 2017, 12:50:15
Imi poate spune cineva, va rog, cu ce am gresit la bitset?
http://www.infoarena.ro/job_detail/1841098?action=view-source --> Aici am folosit bitset pentru ciur si am luat doar 20 puncte
http://www.infoarena.ro/job_detail/1841105?action=view-source --> Aici am folosit char  pentru ciur si am luat 100 de puncte..
Asta e singura diferenta intre cele doua surse.
Multumesc anticipat!


Titlul: Răspuns: 023 Numere Prime
Scris de: Andi Arnautu din Ianuarie 05, 2017, 13:36:45
Cod:
for(long long j = i * i; j <= DIM; j += i) {
                CE[j] = 1;
            }

In codul tau iterezi cu j-ul pana la DIM, ceea ce e gresit, fiindca containerul bitset e indexat de la 0 la DIM - 1, si atunci cand ajungi exact in DIM, accesezi aiurea, ceea ce conduce la greseli. Acelasi lucru il faci si in sursa cu char, dar aparent acolo nu are aceleasi urmari. :P ;)



Titlul: Răspuns: 023 Numere Prime
Scris de: Daniel Rusu din Ianuarie 05, 2017, 16:36:33
e indexat de la 0 la DIM - 1, si atunci cand ajungi exact in DIM, accesezi aiurea, ceea ce conduce la greseli.

Cat noroc am avut  ](*,) ..mersi mult  :thumbup:


Titlul: Răspuns: 023 Numere Prime
Scris de: Mucenic Ion Viorel din Ianuarie 07, 2018, 17:23:37
#include <iostream>
using namespace std;
long i=2,k,n=1,ok=1;
long sum(int i)
{
    int j,s=0;
    for(j=1;j<i;j++)
        if(i%j==0)
        s=s+j;
    return s;
}
int main()
{
    cout<<"k=";
    cin>>k;
    while(n<=k)
    {
        if(i==sum(i)+1)
            n++;
        else
            i++;
    }
    cout<<n;
    while(i<=LONG_MAX||ok==1)
    {
     if(n%i==0&&i==sum(i)+1)
        i++;
     else
        ok=0;
    }
    cout<<i;
    return 0;
}
de ce nu merge?


Titlul: Răspuns: 023 Numere Prime
Scris de: Cojocaru Claudiu Alexandru din Ianuarie 28, 2019, 12:51:27
e normal sa am un timp de 0,0000123? ???


Titlul: Răspuns: 023 Numere Prime
Scris de: Cojocaru Claudiu Alexandru din Ianuarie 28, 2019, 12:51:47
e normal sa am un timp de 0,0000123? ???