52 lines
1.2 KiB
C++
52 lines
1.2 KiB
C++
#include <cassert>
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
class totient_calculator {
|
|
public:
|
|
explicit totient_calculator(int max) : totient_(max + 1) {
|
|
for (int i = 1; i <= max; ++i)
|
|
totient_[i] = i;
|
|
for (int i = 2; i <= max; ++i) {
|
|
if (totient_[i] < i)
|
|
continue;
|
|
for (int j = i; j <= max; j += i)
|
|
totient_[j] -= totient_[j] / i;
|
|
}
|
|
}
|
|
int totient(int n) const {
|
|
assert (n >= 1 && n < totient_.size());
|
|
return totient_[n];
|
|
}
|
|
bool is_prime(int n) const {
|
|
return totient(n) == n - 1;
|
|
}
|
|
private:
|
|
std::vector<int> totient_;
|
|
};
|
|
|
|
bool perfect_totient_number(const totient_calculator& tc, int n) {
|
|
int sum = 0;
|
|
for (int m = n; m > 1; ) {
|
|
int t = tc.totient(m);
|
|
sum += t;
|
|
m = t;
|
|
}
|
|
return sum == n;
|
|
}
|
|
|
|
int main() {
|
|
totient_calculator tc(10000);
|
|
int count = 0, n = 1;
|
|
std::cout << "First 20 perfect totient numbers:\n";
|
|
for (; count < 20; ++n) {
|
|
if (perfect_totient_number(tc, n)) {
|
|
if (count > 0)
|
|
std::cout << ' ';
|
|
++count;
|
|
std::cout << n;
|
|
}
|
|
}
|
|
std::cout << '\n';
|
|
return 0;
|
|
}
|