Napiši program koji za dati prirodan broj \(n\) određuje koliko ima parova prostih brojeva \((p, q)\) takvih da je \(p < q\) i \(p+q \leq n\) je takođe prost.
Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 10^6\)).
Na standardni izlaz ispisati traženi broj parova, takav da je \(p+q \leq n\).
6
1
Jedini par koji zadovoljava uslove je \((2, 3)\), jer je \(5 \leq 6\) prost broj.
100
8
Rešenje grubom silom podrazumeva da se za svaki par brojeva \(2 \leq p < q \leq n - p\) proveri da li ispunjava uslove zadatka. Nabrajanje parova možemo vršiti ugnežđenim petljama, a proveru da li je broj prost algoritmom koji proverava da li je broj prost.
Pošto se provera da li je dati broj prost realizuje u vremenu \(O(\sqrt{n})\), a takvih parova ima \(O(n^2)\), složenost ovog pristupa je \(O(n^2 \sqrt{n})\).
Jednu malu optimizaciju možemo postići korišćenjem odsecanja – ako broj \(p\) nije prost, nema potrebe da pokrećemo unutrašnju petlju i da proveravamo različite vrednosti \(q\). Pošto prostih brojeva manjih od \(n\) ima otprilike \(\frac{n}{\log{n}}\), ovim se program ubrzava asimptotski, ali, nažalost, samo za faktor \(\log{n}\).
#include <iostream>
#include <vector>
using namespace std;
bool is_prime(const int n)
{
if (n < 2) {
return false;
}
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) {
return false;
}
}
return true;
}
int main()
{
int n; cin >> n;
int count = 0;
for (int p = 2; p <= n; p++) {
if (is_prime(p)) {
for (int q = p + 1; p + q <= n; q++) {
if (is_prime(q) && is_prime(p + q)) {
count++;
}
}
}
}
cout << count << endl;
return 0;
}Određivanje svih prostih brojeva iz intervala \([0, n]\) možemo uraditi efikasno Eratostenovim sitom. Nakon toga za sve parove \(2 \leq p < q \leq n - p\) možemo proveriti da li zadovoljavaju uslov tako što proveru primalnosti jako brzo vršimo na osnovu niza koji je izgenerisan postupkom Eratostenovog sita.
Složenost Eratostenovog sita je \(O(n\log{\log{n}})\). Nakon konstrukcije niza, za svaki element možemo u u konstantnoj složenosti proveriti da li je prost. Međutim, parova kandidata ima \(O(n^2)\), pa vremenom izvršavanja dominira faza provere svih parova i ukupna složenost je \(O(n^2)\).
#include <iostream>
#include <vector>
using namespace std;
vector<bool> sieve(const int n)
{
vector<bool> is_prime(n + 1, true);
is_prime[0] = false;
is_prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
return is_prime;
}
int main()
{
int n; cin >> n;
auto is_prime = sieve(n);
int count = 0;
for (int p = 2; p <= n; p++) {
if (is_prime[p]) {
for (int q = p + 1; p + q <= n; q++) {
if (is_prime[q] && is_prime[p + q]) {
count++;
}
}
}
}
cout << count << endl;
return 0;
}Efikasnost se značajno može popraviti odsecanjem. Naime, može se primetiti da ako su \(p\) i \(q\) prosti brojevi veći od \(2\), oni su neparni, a zbir dva neparna broja je paran broj, koji je sigurno veći od \(2\). Zato njihov zbir ne može da bude prost. Odatle sledi da broj \(p\) sigurno mora da bude jednak \(2\), a pitanje se svodi na pronalaženje svih brojeva \(2 < q \leq n - 2\), takvih da su \(q\) i \(q+2\) prosti (to su takozvani prosti brojevi blizanci).
Određivanje svih prostih brojeva manjih ili jednakih od \(n\) možemo uraditi Eratostenovim sitom, u vremenu \(O(n \log{\log{n}})\). Nakon toga pronalazak parova blizanaca možemo uraditi u dodatnom vremenu \(O(n)\), tako da Eratostenovo sito dominira celim algoritmom.
#include <iostream>
#include <vector>
using namespace std;
vector<bool> sieve(const int n)
{
vector<bool> is_prime(n + 1, true);
is_prime[0] = false;
is_prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
return is_prime;
}
int main()
{
int n; cin >> n;
auto is_prime = sieve(n);
int count = 0;
int p = 2;
for (int q = p + 1; p + q <= n; q++) {
if (is_prime[q] && is_prime[p + q]) {
count++;
}
}
cout << count << endl;
return 0;
}