Factors of a Mersenne number: Difference between revisions
C++ - no need to use a sieve in this case
m (Minor edit to C++ code) |
(C++ - no need to use a sieve in this case) |
||
Line 546:
#include <cstdint>
#include <vector>
typedef uint64_t integer;
Line 571 ⟶ 570:
}
return false;▼
}▼
return true;
}▼
integer find_mersenne_factor(
integer k = 0;
integer q = 1;
Line 579 ⟶ 588:
++k;
q = 2 * k * p + 1;
▲ if (q >= limit)
▲ break;
if (q % 8 == 1 || q % 8 == 7) {
if (mod_pow(p, q) == 1 &&
return q;
}
Line 590 ⟶ 597:
int main() {
▲ std::cout << find_mersenne_factor(sieve, 929) << '\n';
return 0;
}</lang>
▲ if (n == 2)
▲ return true;
▲ if (n < 2 || n % 2 == 0)
▲ return false;
▲}
▲ for (size_t p = 3; p * p <= limit; p += 2) {
▲ }
{{out}}
| |||