Cod sursa(job #3273706)
| Utilizator | Data | 3 februarie 2025 16:28:23 | |
|---|---|---|---|
| Problema | Fractii | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.61 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("fractii.in");
ofstream out("fractii.out");
bool isPrime(int n) {
if (n < 2) return 0;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
int main() {
long long n;
in >> n;
long long cnt_pairs = 0;
for (long long i = 2; i <= n; i++) {
if (isPrime(i)) {
long long prime_divs = n / i;
cnt_pairs += prime_divs * (prime_divs - 1);
}
}
long long sol = 1 + n * (n - 1) - cnt_pairs;
out << sol;
return 0;
}