A circular prime number is a number that remains prime on any cyclic
rotation of its digits. For our purposes, we're only interested in numbers of
base 10 (i.e., decimal-based numbers).
Any one-digit prime is circular by default. Thus, the circular one-digit primes are: 2, 3, 5 and 7. For multi-digit numbers, the digits can only consist of the numbers 1, 3, 7 and 9, since any even digit will eventually be rotated to the unit's place and make the number even, and any number ending with 5 is divisible by the circular prime number 5. A number consisting entirely of 1s is called a RepUnit (i.e., repetitive unit - denoted as R _{n}) and is not discussed in detail here. These
types of circular primes are easier to factor than the non-RepUnit ones due to
Fermat's Little Theorem and other optimized algorithms. One requirement,
however, is that the number of units has to be prime.
R _{m*n} = (10^{m*n} - 1) /9
= ((10
^{m} - 1) / 9) * (10^{m*(n - 1)} +
10^{m*(n - 2)} + … + 10^{m} + 1)= R
_{m} * (10^{m*(n - 1)} + 10^{m*(n -
2)} + … + 10^{m} + 1)Visually, n R _{m}'s concatenated together would form an
R_{m*n}, as would m R_{n}'s.
11111 11111 … 11111 = R_{m*n}
R _{m}
R_{m}
R_{m}Hence, R _{n} is prime only if n is prime.
The current list of circular primes are: 2, 3, 5, 7, 11 (R
_{2}), 13, 17, 37, 79, 113, 197, 199,
337, 1193, 3779, 11939, 19937, 193939, 199933, R_{19}, R_{23},
R_{317}, and R_{1031}.A few more potential circular primes are: R
_{49081} and R_{86453}. |

This is probably the easiest method to implement.

With the exception of the numbers 2 and 5, the digits of any circular prime have to be 1, 3, 7, or 9.

Since we're trying to optimize the algorithm, let us assume the following decimal-to-binary, one-to-one mapping:

- 1 ↔ 00
- 3 ↔ 01
- 7 ↔ 10
- 9 ↔ 11

Thus, for two-digit numbers,

- 0 ↔ 0000 ↔ 11
- 1 ↔ 0001 ↔ 13
- 2 ↔ 0010 ↔ 17
- 3 ↔ 0011 ↔ 19
- 4 ↔ 0100 ↔ 31
- 5 ↔ 0101 ↔ 33
- 6 ↔ 0110 ↔ 37
- 7 ↔ 0111 ↔ 39
- 8 ↔ 1000 ↔ 71
- 9 ↔ 1001 ↔ 73
- 10 ↔ 1010 ↔ 77
- 11 ↔ 1011 ↔ 79
- 12 ↔ 1100 ↔ 91
- 13 ↔ 1101 ↔ 93
- 14 ↔ 1110 ↔ 97
- 15 ↔ 1111 ↔ 99

Let's look at 32-bit binary numbers.

Assume, n = 677643.

0FEDCBA9876543210FEDCBA987654321 = 32 bits

000000000000101001010111000010__11__ = 677643 ↔
7733391179

000000000000__11__101001010111000010 = 955842 ↔
9773339117

Thus, to rotate any integer with n digits, we just perform a couple of bitwise shifts on the current integer and compare the new one with the old.

Let number = 677643, then n = 6.

Then, rotated number = (number >> 2) + ((number &
0x3) << (2 * (n - 1))) = 955842.

Since, 955842 > 677643, we continue rotating. If all
rotations are greater than the original number, then the number and all its
rotations are tested for primality. If at any rotation the number is less than
or equal to the original number, we break out of the rotation loop and move on
to the next number.

This works well when testing 32 and 64-bit decimal numbers, or digits up to length 16 and 32.

Method #1 can be combined with a linked list to speed up the search and remove method.

To search for 3-digit circular numbers, we first create a list of all 3-digit numbers that begin with 1.

Then, to find the 3-digit numbers that begin with 3, we start searching through the list of numbers beginning with 1 from 133.

Next, we find the 3-digit numbers that begin with 7 by searching through the list of numbers beginning with 3 found from 377.

Since 333 and 777 are divisible by 3 and 7, respectively, we can just as easily skip those numbers. If the number is 0, then no rotation is performed, and a special algorithm to check primality for RepUnits is used.

This method can easily be extended to search for circular primes of any size.

__Note__: There are no circular primes that begin with 9.

0 | 000000 | 16 | 010000 | 32 | 100000 | 48 | 110000 |

1 | 000001 | 17 | 010001 | 33 | 100001 | 49 | 110001 |

2 | 000010 | 18 | 010010 | 34 | 100010 | 50 | 110010 |

3 | 000011 | 19 | 010011 | 35 | 100011 | 51 | 110011 |

4 | 000100 | 20 | 010100 | 36 | 100100 | 52 | 110100 |

5 | 000101 | 21 | 010101 | 37 | 100101 | 53 | 110101 |

6 | 000110 | 22 | 010110 | 38 | 100110 | 54 | 110110 |

7 | 000111 | 23 | 010111 | 39 | 100111 | 55 | 110111 |

8 | 001000 | 24 | 011000 | 40 | 101000 | 56 | 111000 |

9 | 001001 | 25 | 011001 | 41 | 101001 | 57 | 111001 |

10 | 001010 | 26 | 011010 | 42 | 101010 | 58 | 111010 |

11 | 001011 | 27 | 011011 | 43 | 101011 | 59 | 111011 |

12 | 001100 | 28 | 011100 | 44 | 101100 | 60 | 111100 |

13 | 001101 | 29 | 011101 | 45 | 101101 | 61 | 111101 |

14 | 001110 | 30 | 011110 | 46 | 101110 | 62 | 111110 |

15 | 001111 | 31 | 011111 | 47 | 101111 | 63 | 111111 |

This is probably the most efficient method.

Let's assume we're checking all primes with a fixed number of digits (n),
and we're starting at R_{n}. Without loss of generality, let's assume n
= 6. Then our sequence is 111111 → 111113 → 111117 → 111119.
From 111119, we go to 111133, since starting at 111131 would imply a rotation
111113 that is already covered. The unit digit can only be equal to the
leading digit when all the digits are 1 (R_{n}), otherwise it is
divisible by 3, 7, or 9.

To assure numbers that cannot be rotated into smaller numbers, whenever we're about to increment the last 9, from the unit's end, we add 2 to the digit before it (and skip over 5s) and concatenate the remaining digits from the beginning and increment the unit digit by 2. If the number before that is 9, we increment the first non-9 before that and concatenate the rest from the beginning (i.e., 191999 → 193999 → 193193 → 193197, with the two middle steps shown for comprehension).

Thus, we guarantee no smaller number on rotation.

- The Prime Glossary (Circular Primes)
- World! of Numbers (Circular Primes)
- World! of Numbers (RepUnits)