Salut din nou.
O problema de ‘incepator’ dupa infoarena..
Suna cam asa:
Gheorghe a invatat la scoala despre numere prime. A invatat ca un numar este prim, daca se divide doar cu 1 si cu el insusi(1 nu este considerat numar prim). A aflat ca exista algoritimi foarte eficienti care pot determina daca un numar este prim sau nu, in timp chiar sub polinomial. Din pacate acesti algoritmi sunt foarte complicati, si Gheorghe s-a gandit la o aproximare. Idea lui este sa consideri un numar prim daca nu se divide la primele K numere prime.
Cerinta
Demonstreaza ca ideea lui Gheorghe este doar o aproximare. Dandu-se un numar K, afla cel mai mic numar N care nu este divizibil cu primele K numere prime, dar nu este prim.
Date de intrare
Pe prima linie din fisierul prim.in se va afla numarul K.
Date de iesire
Pe prima linie a fisierului prim.out se va gasi numarul N cautat.
Restrictii
1 ≤ K ≤ 100.000
Exemplu: prim.in 1 prim.out 9
Explicatii
9 nu este divizibil cu 2 si nu este nici prim.prim.in
Exemplu: prim.in 3 prim.out 49
Explicatii
Primele 3 numere prime sunt 2, 3, 5. Numerele care nu sunt divizibile 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.
Cum am gandit eu rezolvarea ?
Pai trebuie sa afisezi patratul al (K+1)-lea nr. prim ( Ex: k=3, se va afisa 7*7=49).
De asemenea, un prieten mi-a explicat ca el a rezolvat de 100 de pct folosind Ciurul lui Erathostene si inmultire pe numere mari.
Am incercat eu mai multe,am stat ceva timp pr problema,dar..mai mult de 50 pct nu am scos..si asta fara sa folosesc ciuru’…
Cum as putea face ?
A..si asta e sursa aia a mea de 50 pct…imi iese din timp pentru celelalte teste ,nu cred ca ajuta la ceva…..
#include<iostream.h> #include<fstream.h> #include<math.h> ifstream f ("prim.in"); ofstream g("prim.out"); int main() { long long int k,i,j,ok,n,v[100000]; f >> k; f.close(); n=1; cout<<"k="<<k<<endl; for (i=1; i<=k+1; i++) { do { n=n+1; ok=0; for (j=2; j<=sqrt(n); j++) if (n%j==0) ok=1; } while (ok==1); v[i]=n; } g<<v[k+1]*v[k+1]<<" "; g.close(); }
Multumesc ca ai citit atata !!!
Pai foloseste ciurul. Exista o implementare naiva a lui si una optima…Cred ca si cea naiva ar merge in prb ta. Daca vrei ti-o scriu pe cea naiva…iar daca n-o sa-ti mearga cu ea…iti dau link-ul sau functia care o calculeaza optim, depinde acuma cum vrei. Avand in vdr ca se lucreaza cu nr mari o sa-ti iasa mereu din program. TLE (time limit exceeded). Banuiesc ca ai luat prb de pe infoarena.ro nu? Astept sa-mi zici ce preferi.
Multumesc de raspuns, dar am reusit sa o rezolv !😀