33 lines
884 B
C++
33 lines
884 B
C++
#include <iostream>
|
|
|
|
// Assumes n is even with exactly one factor of 2.
|
|
bool is_giuga(unsigned int n) {
|
|
unsigned int m = n / 2;
|
|
auto test_factor = [&m, n](unsigned int p) -> bool {
|
|
if (m % p != 0)
|
|
return true;
|
|
m /= p;
|
|
return m % p != 0 && (n / p - 1) % p == 0;
|
|
};
|
|
if (!test_factor(3) || !test_factor(5))
|
|
return false;
|
|
static constexpr unsigned int wheel[] = {4, 2, 4, 2, 4, 6, 2, 6};
|
|
for (unsigned int p = 7, i = 0; p * p <= m; ++i) {
|
|
if (!test_factor(p))
|
|
return false;
|
|
p += wheel[i & 7];
|
|
}
|
|
return m == 1 || (n / m - 1) % m == 0;
|
|
}
|
|
|
|
int main() {
|
|
std::cout << "First 5 Giuga numbers:\n";
|
|
// n can't be 2 or divisible by 4
|
|
for (unsigned int i = 0, n = 6; i < 5; n += 4) {
|
|
if (is_giuga(n)) {
|
|
std::cout << n << '\n';
|
|
++i;
|
|
}
|
|
}
|
|
}
|