Tutorialspoint.dev

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 <bits/stdc++.h>
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.

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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter