99 lines
2.2 KiB
C
99 lines
2.2 KiB
C
#include <stdbool.h>
|
|
#include <stdint.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <gmp.h>
|
|
|
|
bool is_prime(uint32_t n) {
|
|
if (n == 2)
|
|
return true;
|
|
if (n < 2 || n % 2 == 0)
|
|
return false;
|
|
for (uint32_t p = 3; p * p <= n; p += 2) {
|
|
if (n % p == 0)
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// e.g. returns 2341 if n = 1234
|
|
uint32_t cycle(uint32_t n) {
|
|
uint32_t m = n, p = 1;
|
|
while (m >= 10) {
|
|
p *= 10;
|
|
m /= 10;
|
|
}
|
|
return m + 10 * (n % p);
|
|
}
|
|
|
|
bool is_circular_prime(uint32_t p) {
|
|
if (!is_prime(p))
|
|
return false;
|
|
uint32_t p2 = cycle(p);
|
|
while (p2 != p) {
|
|
if (p2 < p || !is_prime(p2))
|
|
return false;
|
|
p2 = cycle(p2);
|
|
}
|
|
return true;
|
|
}
|
|
|
|
void test_repunit(uint32_t digits) {
|
|
char* str = malloc(digits + 1);
|
|
if (str == 0) {
|
|
fprintf(stderr, "Out of memory\n");
|
|
exit(1);
|
|
}
|
|
memset(str, '1', digits);
|
|
str[digits] = 0;
|
|
mpz_t bignum;
|
|
mpz_init_set_str(bignum, str, 10);
|
|
free(str);
|
|
if (mpz_probab_prime_p(bignum, 10))
|
|
printf("R(%u) is probably prime.\n", digits);
|
|
else
|
|
printf("R(%u) is not prime.\n", digits);
|
|
mpz_clear(bignum);
|
|
}
|
|
|
|
int main() {
|
|
uint32_t p = 2;
|
|
printf("First 19 circular primes:\n");
|
|
for (int count = 0; count < 19; ++p) {
|
|
if (is_circular_prime(p)) {
|
|
if (count > 0)
|
|
printf(", ");
|
|
printf("%u", p);
|
|
++count;
|
|
}
|
|
}
|
|
printf("\n");
|
|
printf("Next 4 circular primes:\n");
|
|
uint32_t repunit = 1, digits = 1;
|
|
for (; repunit < p; ++digits)
|
|
repunit = 10 * repunit + 1;
|
|
mpz_t bignum;
|
|
mpz_init_set_ui(bignum, repunit);
|
|
for (int count = 0; count < 4; ) {
|
|
if (mpz_probab_prime_p(bignum, 15)) {
|
|
if (count > 0)
|
|
printf(", ");
|
|
printf("R(%u)", digits);
|
|
++count;
|
|
}
|
|
++digits;
|
|
mpz_mul_ui(bignum, bignum, 10);
|
|
mpz_add_ui(bignum, bignum, 1);
|
|
}
|
|
mpz_clear(bignum);
|
|
printf("\n");
|
|
test_repunit(5003);
|
|
test_repunit(9887);
|
|
test_repunit(15073);
|
|
test_repunit(25031);
|
|
test_repunit(35317);
|
|
test_repunit(49081);
|
|
return 0;
|
|
}
|