Spunem că un numar natural x este prim dacă și numai daca x > 1 si singurii săi divizori sunt 1 si x. Dându-se un numar natural N (2 ≤ N ≤ 2 000 000), să se determine numărul numerelor prime mai mici sau egale cu N.
Date de intrare
Fișierul de intrare ciur.in conține o singură linie pe care se află numarul N.
Date de ieşire
In fisierul de iesire ciur.out se va scrie pe prima linie raspunsul cerut.
Exemplu
Dacă fișierul de intrare conține numărul 10, în fișierul de ieșire va trebui să apară numărul 4.
Ideea de baza
În primul rând vom da fiecărui element din vector valoarea 1, presupunând astfel că el este prim. Poziția unui element din vector va reprezenta chiar acel număr. Vectorul este alcătuit din variabile booleene, astfel, dacă valoarea lui a[i] este egală cu 1, atunci numărul i este prim.
Rezolvarea
Vom folosi două cicluri for pentru a determina dacă numărul este prim sau nu. Primul începe de la 2 și continuă până la radical din n. Al doilea este inclus în primul și face parcurgerea de la i până la n/i. Apoi, fiecare număr care se obține prin intermediul produsului acestor 2 numere este eliminat, el nemaiputând fi prim pentru că are divizori. În sfârșit, un for final va parcurge vectorul de la 2 până la n, iar pentru fiecare număr a cărui corespondent din vector este 1 contorul (inițializat cu 0) va fi incrementat. Apoi se va face afișarea contorului, adică a numărului de numere prime mai mici ca n.
Codul
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <fstream>#include <math.h>using namespace std;int main() {ifstream fin;ofstream fout;fin.open("ciur.in");fout.open("ciur.out");bool a[2000001];int nr=0, n, i, j;fin>>n;for (i=2;i<=n;i++) a[i]=1;for (i=2;i<=sqrt(n);i++) if (a[i]) for (j=i;j<=n/i;j++) a[i*j]=0;for (i=2;i<=n;i++) if (a[i]) nr++;fout<<nr;fout.close();return 0;} |
Problemă demonstrativă
Ionel a învățat la școală despre numere prime. A învățat că un număr este prim, dacă se divide doar cu 1 și cu el însuși(1 nu este considerat număr prim). A aflat că există algoritimi foarte eficienți care pot determina dacă un număr este prim sau nu, în timp chiar sub polinomial. Din păcate acești algoritmi sunt foarte complicați, și Ionel s-a gândit la o aproximare. Ideea lui este să consideri un număr prim dacă nu se divide la primele K numere prime.
Cerinţă
Demonstrează că ideea lui Ionel este doar o aproximare. Dându-se un număr K (1 ≤ K ≤ 100.000), află 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 fişierul prim.in se va afla numărul K.
Date de ieşire
Pe prima linie a fişierului prim.out se va gasi numarul N căutat.
Exemplu
Pentru valoarea 3 ca dată de intrare se va afișa 49, pentru că 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.
Rezolvare
Deoarece nu știm de câte numere vom avea nevoie, am preferat să folosesc un define pentru 1.500.000, acest număr fiind „capătul” vectorului. Până acolo vom face parcurgerea vectorului, aplicând Ciurul lui Eratostene. Variabila nrp desemnează numărul de parcurgeri, astfel, când se ajunge la k+1parcurgeri n va lua valoarea pătratului lui i, până atunci multiplii lui i fiind „eliminaţi”, valoarea lor din vector devenind 0. Condiția de la început if(prim[i]) se asigură că se vor verifica doar numerele reale. Datorită faptului că pătratul unui număr prim nu se poate divide la numărul prim anterior, ne dăm seama că soluția i*i după k+1 parcurgeri este cea corectă.
Codul
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <fstream>#include <math.h>#define INF 1500000using namespace std;bool prim[INF];int main(){ifstream fin("prim.in");ofstream fout("prim.out");long long n,k,nrp,i,j;fin>>k;for(i=2;i<INF;i++) prim[i]=1;for(i=2,nrp=0;i<=INF;i++) if(prim[i]){ if(++nrp==k+1){ n=(long long)i*i; fout<<n; fout.close(); return 0; } for(j=i;j<=INF;j+=i) prim[j]=0; }} |
