41 lines
1 KiB
C
41 lines
1 KiB
C
#include <stdio.h>
|
|
#include <stdbool.h>
|
|
#include <stdint.h>
|
|
#include <locale.h>
|
|
|
|
uint64_t modPow(uint64_t base, uint64_t exp, uint64_t mod) {
|
|
if (mod == 1) return 0;
|
|
uint64_t result = 1;
|
|
base %= mod;
|
|
for (; exp > 0; exp >>= 1) {
|
|
if ((exp & 1) == 1) result = (result * base) % mod;
|
|
base = (base * base) % mod;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
bool isCurzon(uint64_t n, uint64_t k) {
|
|
const uint64_t r = k * n;
|
|
return modPow(k, n, r+1) == r;
|
|
}
|
|
|
|
int main() {
|
|
uint64_t k, n, count;
|
|
setlocale(LC_NUMERIC, "");
|
|
for (k = 2; k <= 10; k += 2) {
|
|
printf("Curzon numbers with base %ld:\n", k);
|
|
for (n = 1, count = 0; count < 50; ++n) {
|
|
if (isCurzon(n, k)) {
|
|
printf("%4ld ", n);
|
|
if (++count % 10 == 0) printf("\n");
|
|
}
|
|
}
|
|
for (;;) {
|
|
if (isCurzon(n, k)) ++count;
|
|
if (count == 1000) break;
|
|
++n;
|
|
}
|
|
printf("1,000th Curzon number with base %ld: %'ld\n\n", k, n);
|
|
}
|
|
return 0;
|
|
}
|