# Circular primes less than n

Find all circular primes less than given number n. A prime number is a Circular Prime Number if all of its possible rotations are itself prime numbers.

Examples :

```79 is a circular prime.
as 79 and 97 are prime numbers.

But 23 is not a circular prime.
as 23 is prime but 32 is not a prime number.
```

Algorithm:

```-> Find prime numbers up to n using Sieve of Sundaram algorithm.
-> Now for every prime number from sieve method,
one after another, we should check whether its all
rotations are prime or not:
-> If yes then print that prime number.
-> If no then skip that prime number.
```

Below is the implementation of the above algorithm :

## C++

 `// C++ program to print primes smaller than n using ` `// Sieve of Sundaram. ` `#include ` `using` `namespace` `std; ` ` `  `// Prototypes of the methods used ` `void` `SieveOfSundaram(``bool` `marked[], ``int``); ` `int` `Rotate(``int``); ` `int` `countDigits(``int``); ` ` `  `// Print all circular primes ` `void` `circularPrime(``int` `n) ` `{ ` `    ``// In general Sieve of Sundaram, produces primes smaller ` `    ``// than (2*x + 2) for a number given number x. ` `    ``// Since we want primes smaller than n, we reduce n to half ` `    ``int` `nNew = (n - 2) / 2; ` ` `  `    ``// This array is used to separate numbers of the form i+j+2ij ` `    ``// from others where 1 <= i <= j ` `    ``bool` `marked[nNew + 1]; ` ` `  `    ``// Initialize all elements as not marked ` `    ``memset``(marked, ``false``, ``sizeof``(marked)); ` ` `  `    ``SieveOfSundaram(marked, nNew); ` ` `  `    ``// if n > 2 then 2 is also a circular prime ` `    ``cout << ``"2 "``; ` ` `  `    ``// According to Sieve of sundaram If marked[i] is false ` `    ``// then 2*i + 1 is a prime number. ` ` `  `    ``// loop to check all  prime numbers and their rotations ` `    ``for` `(``int` `i = 1; i <= nNew; i++) { ` `        ``// Skip this number if not prime ` `        ``if` `(marked[i] == ``true``) ` `            ``continue``; ` ` `  `        ``int` `num = 2 * i + 1; ` `        ``num = Rotate(num); ``// function for rotation of prime ` ` `  `        ``// now we check for rotations of this prime number ` `        ``// if new rotation is prime check next rotation, ` `        ``// till new rotation becomes the actual prime number ` `        ``// and if new rotation if not prime then break ` `        ``while` `(num != 2 * i + 1) { ` `            ``if` `(num % 2 == 0) ``// check for even ` `                ``break``; ` ` `  `            ``// if rotated number is prime then rotate ` `            ``// for next ` `            ``if` `(marked[(num - 1) / 2] == ``false``) ` `                ``num = Rotate(num); ` `            ``else` `                ``break``; ` `        ``} ` ` `  `        ``// if checked number is circular prime print it ` `        ``if` `(num == (2 * i + 1)) ` `            ``cout << num << ``" "``; ` `    ``} ` `} ` ` `  `// Sieve of Sundaram for generating prime number ` `void` `SieveOfSundaram(``bool` `marked[], ``int` `nNew) ` `{ ` `    ``// Main logic of Sundaram. Mark all numbers of the ` `    ``// form i + j + 2ij as true where 1 <= i <= j ` `    ``for` `(``int` `i = 1; i <= nNew; i++) ` `        ``for` `(``int` `j = i; (i + j + 2 * i * j) <= nNew; j++) ` `            ``marked[i + j + 2 * i * j] = ``true``; ` `} ` ` `  `// Rotate function to right rotate the number ` `int` `Rotate(``int` `n) ` `{ ` `    ``int` `rem = n % 10; ``// find unit place number ` `    ``rem *= ``pow``(10, countDigits(n)); ``// to put unit place ` `    ``// number as first digit. ` `    ``n /= 10; ``// remove unit digit ` `    ``n += rem; ``// add first digit to rest ` `    ``return` `n; ` `} ` ` `  `// Function to find total number of digits ` `int` `countDigits(``int` `n) ` `{ ` `    ``int` `digit = 0; ` `    ``while` `(n /= 10) ` `        ``digit++; ` `    ``return` `digit; ` `} ` ` `  `// Driver program to test above ` `int` `main(``void``) ` `{ ` `    ``int` `n = 100; ` `    ``circularPrime(n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to print primes smaller ` `// than n using Sieve of Sundaram. ` `import` `java.util.Arrays; ` `class` `GFG { ` ` `  `    ``// Print all circular primes ` `    ``static` `void` `circularPrime(``int` `n) ` `    ``{ ` `        ``// In general Sieve of Sundaram, produces ` `        ``// primes smaller than (2*x + 2) for a ` `        ``// number given number x.Since we want ` `        ``// primes smaller than n, we reduce n to half ` `        ``int` `nNew = (n - ``2``) / ``2``; ` ` `  `        ``// This array is used to separate numbers of the ` `        ``// form i+j+2ij from others where 1 <= i <= j ` `        ``boolean` `marked[] = ``new` `boolean``[nNew + ``1``]; ` ` `  `        ``// Initialize all elements as not marked ` `        ``Arrays.fill(marked, ``false``); ` ` `  `        ``SieveOfSundaram(marked, nNew); ` ` `  `        ``// if n > 2 then 2 is also a circular prime ` `        ``System.out.print(``"2 "``); ` ` `  `        ``// According to Sieve of sundaram If marked[i] is false ` `        ``// then 2*i + 1 is a prime number. ` ` `  `        ``// loop to check all prime numbers and their rotations ` `        ``for` `(``int` `i = ``1``; i <= nNew; i++) { ` `            ``// Skip this number if not prime ` `            ``if` `(marked[i] == ``true``) ` `                ``continue``; ` ` `  `            ``int` `num = ``2` `* i + ``1``; ` `            ``num = Rotate(num); ``// function for rotation of prime ` ` `  `            ``// now we check for rotations of this prime number ` `            ``// if new rotation is prime check next rotation, ` `            ``// till new rotation becomes the actual prime number ` `            ``// and if new rotation if not prime then break ` `            ``while` `(num != ``2` `* i + ``1``) { ` `                ``if` `(num % ``2` `== ``0``) ``// check for even ` `                    ``break``; ` ` `  `                ``// if rotated number is prime then rotate ` `                ``// for next ` `                ``if` `(marked[(num - ``1``) / ``2``] == ``false``) ` `                    ``num = Rotate(num); ` `                ``else` `                    ``break``; ` `            ``} ` ` `  `            ``// if checked number is circular prime print it ` `            ``if` `(num == (``2` `* i + ``1``)) ` `                ``System.out.print(num + ``" "``); ` `        ``} ` `    ``} ` ` `  `    ``// Sieve of Sundaram for generating prime number ` `    ``static` `void` `SieveOfSundaram(``boolean` `marked[], ``int` `nNew) ` `    ``{ ` `        ``// Main logic of Sundaram. Mark all numbers of the ` `        ``// form i + j + 2ij as true where 1 <= i <= j ` `        ``for` `(``int` `i = ``1``; i <= nNew; i++) ` `            ``for` `(``int` `j = i; (i + j + ``2` `* i * j) <= nNew; j++) ` `                ``marked[i + j + ``2` `* i * j] = ``true``; ` `    ``} ` ` `  `    ``// Function to find total number of digits ` `    ``static` `int` `countDigits(``int` `n) ` `    ``{ ` `        ``int` `digit = ``0``; ` `        ``while` `((n /= ``10``) > ``0``) ` `            ``digit++; ` `        ``return` `digit; ` `    ``} ` ` `  `    ``// Rotate function to right rotate the number ` `    ``static` `int` `Rotate(``int` `n) ` `    ``{ ` `        ``int` `rem = n % ``10``; ``// find unit place number ` `        ``rem *= Math.pow(``10``, countDigits(n)); ``// to put unit place ` `        ``// number as first digit. ` `        ``n /= ``10``; ``// remove unit digit ` `        ``n += rem; ``// add first digit to rest ` `        ``return` `n; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `n = ``100``; ` `        ``circularPrime(n); ` `    ``} ` `} ` `// This code is contributed by Anant Agarwal. `

/div>

## C#

 `// C# program to print primes smaller ` `// than n using Sieve of Sundaram. ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Print all circular primes ` `    ``static` `void` `circularPrime(``int` `n) ` `    ``{ ` `        ``// In general Sieve of Sundaram, produces ` `        ``// primes smaller than (2*x + 2) for a ` `        ``// number given number x.Since we want ` `        ``// primes smaller than n, we reduce n to half ` `        ``int` `nNew = (n - 2) / 2; ` ` `  `        ``// This array is used to separate numbers of the ` `        ``// form i+j+2ij from others where 1 <= i <= j ` `        ``bool``[] marked = ``new` `bool``[nNew + 1]; ` ` `  `        ``// Initialize all elements as not marked ` `        ``// Arrays.fill(marked, false); ` ` `  `        ``SieveOfSundaram(marked, nNew); ` ` `  `        ``// if n > 2 then 2 is also a circular prime ` `        ``Console.Write(``"2 "``); ` ` `  `        ``// According to Sieve of sundaram If  ` `        ``// marked[i] is false then 2*i + 1 is a ` `        ``// prime number. ` ` `  `        ``// loop to check all prime numbers  ` `        ``// and their rotations ` `        ``for` `(``int` `i = 1; i <= nNew; i++) { ` `             `  `            ``// Skip this number if not prime ` `            ``if` `(marked[i] == ``true``) ` `                ``continue``; ` ` `  `            ``int` `num = 2 * i + 1; ` `             `  `            ``// function for rotation of prime ` `            ``num = Rotate(num);  ` ` `  `            ``// now we check for rotations of this prime number ` `            ``// if new rotation is prime check next rotation, ` `            ``// till new rotation becomes the actual prime number ` `            ``// and if new rotation if not prime then break ` `            ``while` `(num != 2 * i + 1) { ` `                ``if` `(num % 2 == 0) ``// check for even ` `                    ``break``; ` ` `  `                ``// if rotated number is prime ` `                ``// then rotate for next ` `                ``if` `(marked[(num - 1) / 2] == ``false``) ` `                    ``num = Rotate(num); ` `                ``else` `                    ``break``; ` `            ``} ` ` `  `            ``// if checked number is circular prime print it ` `            ``if` `(num == (2 * i + 1)) ` `                ``Console.Write(num + ``" "``); ` `        ``} ` `    ``} ` ` `  `    ``// Sieve of Sundaram for generating prime number ` `    ``static` `void` `SieveOfSundaram(``bool``[] marked, ``int` `nNew) ` `    ``{ ` `        ``// Main logic of Sundaram. Mark all numbers of the ` `        ``// form i + j + 2ij as true where 1 <= i <= j ` `        ``for` `(``int` `i = 1; i <= nNew; i++) ` `            ``for` `(``int` `j = i; (i + j + 2 * i * j) <= nNew; j++) ` `                ``marked[i + j + 2 * i * j] = ``true``; ` `    ``} ` ` `  `    ``// Function to find total number of digits ` `    ``static` `int` `countDigits(``int` `n) ` `    ``{ ` `        ``int` `digit = 0; ` `        ``while` `((n /= 10) > 0) ` `            ``digit++; ` `        ``return` `digit; ` `    ``} ` ` `  `    ``// Rotate function to right rotate the number ` `    ``static` `int` `Rotate(``int` `n) ` `    ``{ ` `        ``// find unit place number ` `        ``int` `rem = n % 10;  ` `         `  `        ``// to put unit place ` `        ``rem *= (``int``)Math.Pow(10, countDigits(n)); ` `         `  `        ``// number as first digit. ` `        ``n /= 10; ``// remove unit digit ` `        ``n += rem; ``// add first digit to rest ` `        ``return` `n; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 100; ` `        ``circularPrime(n); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

2 then 2 is also a circular prime
print(“2 “);

// According to Sieve of sundaram If marked[i]
// is false then 2*i + 1 is a prime number.

// loop to check all prime numbers
// and their rotations
for (\$i = 1; \$i <= \$nNew; \$i++) { // Skip this number if not prime if (\$marked[\$i] == true) continue; \$num = 2 * \$i + 1; \$num = Rotate(\$num); // function for rotation of prime // now we check for rotations of this // prime number if new rotation is prime // check next rotation, till new rotation // becomes the actual prime number and if // new rotation if not prime then break while (\$num != 2 * \$i + 1) { if (\$num % 2 == 0) // check for even break; // if rotated number is prime then // rotate for next if (\$marked[(int)((\$num - 1) / 2)] == false) \$num = Rotate(\$num); else break; } // if checked number is circular // prime print it if (\$num == (2 * \$i + 1)) print(\$num." "); } } // Sieve of Sundaram for generating prime number function SieveOfSundaram(&\$marked, \$nNew) { // Main logic of Sundaram. Mark all numbers of the // form i + j + 2ij as true where 1 <= i <= j for (\$i = 1; \$i <= \$nNew; \$i++) for (\$j = \$i; (\$i + \$j + 2 * \$i * \$j) <= \$nNew; \$j++) \$marked[\$i + \$j + 2 * \$i * \$j] = true; } // Rotate function to right rotate the number function Rotate(\$n) { \$rem = \$n % 10; // find unit place number \$rem *= pow(10, countDigits(\$n)); // to put unit place // number as first digit. \$n = (int)(\$n / 10); // remove unit digit \$n += \$rem; // add first digit to rest return \$n; } // Function to find total number of digits function countDigits(\$n) { \$digit = 0; \$n = (int)(\$n / 10); while (\$n) { \$digit++; \$n = (int)(\$n / 10); } return \$digit; } // Driver Code \$n = 100; circularPrime(\$n); // This code is contributed by mits ?>

Output:

```2 3 5 7 11 13 17 31 37 71 73 79 97
```