Perfect totient numbers: Difference between revisions
Added C++ solution
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
(Added C++ solution) |
||
Line 137:
The first 40 perfect Totient numbers are :
[ 3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, 5571, 6561, 8751, 15723, 19683, 36759, 46791, 59049, 65535, 140103, 177147, 208191, 441027, 531441, 1594323, 4190263, 4782969, 9056583, 14348907, 43046721, 57395631]
</pre>
=={{header|C++}}==
<lang cpp>#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;
}</lang>
{{out}}
<pre>
First 20 perfect totient numbers:
3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571
</pre>
| |||