Spunem că un număr natural este aproape prim dacă el poate fi scris ca produs de două numere prime. De exemplu 6 și 25 sunt aproape prime pentru că 6 = 2 * 3, iar 25 = 5 * 5. Considerăm șirul crescător al numerelor naturale aproape prime: 4, 6, 9, 10, 14, 15, 21, … Acestora li se asociază câte un număr de ordine, numerotarea începând cu 1. Deci 4 este primul număr aproape prim, 6 este al doilea număr, 9 este al treilea etc.
Cerința
Dat un număr natural N, să se determine al N-lea număr aproape prim.
Date de intrare
Programul citește de la tastatură numărul N.
Date de ieșire
Programul va afișa pe ecran un singur număr natural, reprezentând al N-lea număr aproape prim.
Restricții și precizări
1 ≤ N ≤ 23.378
Exemplul 1:
Intrare
4
Ieșire
10
Exemplul 2:
Intrare
300
Ieșire
1003
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema AproapePrime:
#include <bits/stdc++.h>
using namespace std;
bitset<1000005> b;
bitset<1000005> a;
int prime[80000], k, n;
void Ciur(int n)
{
int i, j;
for (i = 4; i <= n; i += 2)
b[i] = 1;
for (i = 3; i * i <= n; i += 2)
if (b[i] == 0)
for (j = i * i; j <= n; j = j + 2 * i)
b[j] = 1;
k = 1;
prime[1] = 2;
for (i = 3; i <= n; i += 2)
if (b[i] == 0) prime[++k] = i;
}
void AproapePrime()
{
int i, j;
for (i = 1; i <= k; i++)
for (j = i; j <= k && 1LL * prime[i] * prime[j] <= 100000; j++)
a[ prime[i] * prime[j] ] = 1;
int cnt = 0;
for (int i = 4; i <= 100000; i++)
if (a[i] == 1) cnt++;
}
void CitireAfisare()
{
int i;
cin >> n;
for (i = 4; i <= 100000; i++)
if (a[i] == 1)
{
n--;
if (n == 0)
{
cout << i;
return;
}
}
}
int main()
{
Ciur(100000);
AproapePrime();
CitireAfisare();
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #3278 AproapePrime
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3278 AproapePrime de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!