Wieferich primes: Difference between revisions
→{{header|C++}}
(Added Quackery.) |
|||
Line 19:
;* [[oeis:A001220|OEIS A001220 - Wieferich primes]]
<br>
=={{header|C}}==
{{trans|C++}}
<lang c>#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#define LIMIT 5000
static bool PRIMES[LIMIT];
static void prime_sieve() {
uint64_t p;
int i;
PRIMES[0] = false;
PRIMES[1] = false;
for (i = 2; i < LIMIT; i++) {
PRIMES[i] = true;
}
for (i = 4; i < LIMIT; i += 2) {
PRIMES[i] = false;
}
for (p = 3;; p += 2) {
uint64_t q = p * p;
if (q >= LIMIT) {
break;
}
if (PRIMES[p]) {
uint64_t inc = 2 * p;
for (; q < LIMIT; q += inc) {
PRIMES[q] = false;
}
}
}
}
uint64_t modpow(uint64_t base, uint64_t exp, uint64_t mod) {
uint64_t result = 1;
if (mod == 1) {
return 0;
}
base %= mod;
for (; exp > 0; exp >>= 1) {
if ((exp & 1) == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
}
return result;
}
void wieferich_primes() {
uint64_t p;
for (p = 2; p < LIMIT; ++p) {
if (PRIMES[p] && modpow(2, p - 1, p * p) == 1) {
printf("%lld\n", p);
}
}
}
int main() {
prime_sieve();
printf("Wieferich primes less than %d:\n", LIMIT);
wieferich_primes();
return 0;
}</lang>
{{out}}
<pre>Wieferich primes less than 5000:
1093
3511</pre>
=={{header|C++}}==
| |||