Giuga numbers: Difference between revisions
Added C++ solution
m (→{{header|Free Pascal}}: cheating like julia version) |
(Added C++ solution) |
||
Line 25:
<br><br>
=={{header|C++}}==
Based on the Go solution. Takes 26 minutes on my system (Intel Core i5 3.2GHz).
<lang cpp>#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;
}
}
}</lang>
{{out}}
<pre>
First 5 Giuga numbers:
30
858
1722
66198
2214408306
</pre>
=={{header|FreeBASIC}}==
| |||