Рубрики

Круговые простые числа меньше чем n

Найти все круговые простые числа меньше заданного числа n. Простое число является круглым простым числом, если все его возможные повороты сами являются простыми числами.

Примеры :

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. 

Алгоритм:

-> 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.

Ниже приведена реализация вышеуказанного алгоритма:

C ++

// C ++ программа для печати простых чисел меньше n, используя
// Сито сундарама.
#include <bits/stdc++.h>

using namespace std;

  
// Прототипы используемых методов

void SieveOfSundaram(bool marked[], int);

int Rotate(int);

int countDigits(int);

  
// Распечатать все круговые простые числа

void circularPrime(int n)

{

    // В общем сито сундарам, производит простые числа меньше

    // чем (2 * x + 2) для числа данного числа x.

    // Поскольку мы хотим, чтобы простые числа были меньше n, мы уменьшаем n до половины

    int nNew = (n - 2) / 2;

  

    // Этот массив используется для разделения чисел вида i + j + 2ij

    // от других, где 1 <= i <= j

    bool marked[nNew + 1];

  

    // Инициализируем все элементы как не отмеченные

    memset(marked, false, sizeof(marked));

  

    SieveOfSundaram(marked, nNew);

  

    // если n> 2, то 2 также является круговым простым числом

    cout << "2 ";

  

    // Согласно сите сундарама Если помечено [i] является ложным

    // тогда 2 * i + 1 - простое число.

  

    // цикл для проверки всех простых чисел и их поворотов

    for (int i = 1; i <= nNew; i++) {

        // Пропустить это число, если не простое

        if (marked[i] == true)

            continue;

  

        int num = 2 * i + 1;

        num = Rotate(num); // функция вращения простого числа

  

        // теперь мы проверяем вращения этого простого числа

        // если новое вращение является основной проверкой следующего вращения,

        // пока новое вращение не станет фактическим простым числом

        // и если новое вращение, если не простое, то разрыв

        while (num != 2 * i + 1) {

            if (num % 2 == 0) // проверка на четность

                break;

  

            // если повернутое число простое, то повернуть

            // для следующего

            if (marked[(num - 1) / 2] == false)

                num = Rotate(num);

            else

                break;

        }

  

        // если проверенное число - круговое простое число, выведите его

        if (num == (2 * i + 1))

            cout << num << " ";

    }

}

  
// Сито Сундарама для генерации простого числа

void SieveOfSundaram(bool marked[], int nNew)

{

    // Основная логика сундарама. Отметьте все числа

    // формируем i + j + 2ij как true, где 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;

}

  
// Поворот функции вправо повернуть число

int Rotate(int n)

{

    int rem = n % 10; // найти номер места

    rem *= pow(10, countDigits(n)); // разместить место

    // номер как первая цифра

    n /= 10; // удаляем единицу измерения

    n += rem; // добавить первую цифру для отдыха

    return n;

}

  
// Функция для поиска общего количества цифр

int countDigits(int n)

{

    int digit = 0;

    while (n /= 10)

        digit++;

    return digit;

}

  
// Программа драйвера для тестирования выше

int main(void)

{

    int n = 100;

    circularPrime(n);

    return 0;

}

Джава

// Java-программа для печати простых чисел
// чем использую Сито Сундарама.

import java.util.Arrays;

class GFG {

  

    // Распечатать все круговые простые числа

    static void circularPrime(int n)

    {

        // В общем сито сундарам, производит

        // простые числа меньше (2 * x + 2) для

        // номер заданный номер x.Так как мы хотим

        // простые числа меньше n, мы уменьшаем n до половины

        int nNew = (n - 2) / 2;

  

        // Этот массив используется для разделения номеров

        // формируем i + j + 2ij из других, где 1 <= i <= j

        boolean marked[] = new boolean[nNew + 1];

  

        // Инициализируем все элементы как не отмеченные

        Arrays.fill(marked, false);

  

        SieveOfSundaram(marked, nNew);

  

        // если n> 2, то 2 также является круговым простым числом

        System.out.print("2 ");

  

        // Согласно сите сундарама Если помечено [i] является ложным

        // тогда 2 * i + 1 - простое число.

  

        // цикл для проверки всех простых чисел и их поворотов

        for (int i = 1; i <= nNew; i++) {

            // Пропустить это число, если не простое

            if (marked[i] == true)

                continue;

  

            int num = 2 * i + 1;

            num = Rotate(num); // функция вращения простого числа

  

            // теперь мы проверяем вращения этого простого числа

            // если новое вращение является основной проверкой следующего вращения,

            // пока новое вращение не станет фактическим простым числом

            // и если новое вращение, если не простое, то разрыв

            while (num != 2 * i + 1) {

                if (num % 2 == 0) // проверка на четность

                    break;

  

                // если повернутое число простое, то повернуть

                // для следующего

                if (marked[(num - 1) / 2] == false)

                    num = Rotate(num);

                else

                    break;

            }

  

            // если проверенное число - круговое простое число, выведите его

            if (num == (2 * i + 1))

                System.out.print(num + " ");

        }

    }

  

    // Сито Сундарама для генерации простого числа

    static void SieveOfSundaram(boolean marked[], int nNew)

    {

        // Основная логика сундарама. Отметьте все числа

        // формируем i + j + 2ij как true, где 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;

    }

  

    // Функция для поиска общего количества цифр

    static int countDigits(int n)

    {

        int digit = 0;

        while ((n /= 10) > 0)

            digit++;

        return digit;

    }

  

    // Поворот функции вправо повернуть число

    static int Rotate(int n)

    {

        int rem = n % 10; // найти номер места

        rem *= Math.pow(10, countDigits(n)); // разместить место

        // номер как первая цифра

        n /= 10; // удаляем единицу измерения

        n += rem; // добавить первую цифру для отдыха

        return n;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int n = 100;

        circularPrime(n);

    }

}
// Этот код предоставлен Anant Agarwal.

C #

// C # программа для печати простых чисел
// чем использую Сито Сундарама.

using System;

  

class GFG {

  

    // Распечатать все круговые простые числа

    static void circularPrime(int n)

    {

        // В общем сито сундарам, производит

        // простые числа меньше (2 * x + 2) для

        // номер заданный номер x.Так как мы хотим

        // простые числа меньше n, мы уменьшаем n до половины

        int nNew = (n - 2) / 2;

  

        // Этот массив используется для разделения номеров

        // формируем i + j + 2ij из других, где 1 <= i <= j

        bool[] marked = new bool[nNew + 1];

  

        // Инициализируем все элементы как не отмеченные

        // Arrays.fill (отмечен, false);

  

        SieveOfSundaram(marked, nNew);

  

        // если n> 2, то 2 также является круговым простым числом

        Console.Write("2 ");

  

        // Согласно сите сундарама, если

        // отмечено [i] ложно, тогда 2 * i + 1 является

        // простое число.

  

        // цикл для проверки всех простых чисел

        // и их вращения

        for (int i = 1; i <= nNew; i++) {

              

            // Пропустить это число, если не простое

            if (marked[i] == true)

                continue;

  

            int num = 2 * i + 1;

              

            // функция вращения простого числа

            num = Rotate(num); 

  

            // теперь мы проверяем вращения этого простого числа

            // если новое вращение является основной проверкой следующего вращения,

            // пока новое вращение не станет фактическим простым числом

            // и если новое вращение, если не простое, то разрыв

            while (num != 2 * i + 1) {

                if (num % 2 == 0) // проверка на четность

                    break;

  

                // если повернутое число простое

                // затем вращаемся для следующего

                if (marked[(num - 1) / 2] == false)

                    num = Rotate(num);

                else

                    break;

            }

  

            // если проверенное число - круговое простое число, выведите его

            if (num == (2 * i + 1))

                Console.Write(num + " ");

        }

    }

  

    // Сито Сундарама для генерации простого числа

    static void SieveOfSundaram(bool[] marked, int nNew)

    {

        // Основная логика сундарама. Отметьте все числа

        // формируем i + j + 2ij как true, где 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;

    }

  

    // Функция для поиска общего количества цифр

    static int countDigits(int n)

    {

        int digit = 0;

        while ((n /= 10) > 0)

            digit++;

        return digit;

    }

  

    // Поворот функции вправо повернуть число

    static int Rotate(int n)

    {

        // найти номер места

        int rem = n % 10; 

          

        // разместить место

        rem *= (int)Math.Pow(10, countDigits(n));

          

        // номер как первая цифра

        n /= 10; // удаляем единицу измерения

        n += rem; // добавить первую цифру для отдыха

        return n;

    }

  

    // Код драйвера

    public static void Main()

    {

        int n = 100;

        circularPrime(n);

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP-программа для печати простых чисел меньше
// n используя Сито Сундарама.

  
// Распечатать все круговые простые числа

function circularPrime($n)

{

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для числа

    // заданное число х. Так как мы хотим, чтобы простые числа были меньше

    // чем n, мы уменьшаем n до половины

    $nNew = (int)(($n - 2) / 2);

  

    // Этот массив используется для разделения чисел

    // форма i + j + 2ij от других, где 1 <= i <= j

    $marked = array_fill(0, $nNew + 1, false);

  

    SieveOfSundaram($marked, $nNew);

  

    // если n> 2, то 2 также является круговым простым числом

    print("2 ");

  

    // Согласно сите сундарама Если отмечено [i]

    // ложно, тогда 2 * i + 1 - простое число.

  

    // цикл для проверки всех простых чисел

    // и их вращения

    for ($i = 1; $i <= $nNew; $i++) 

    {

        // Пропустить это число, если не простое

        if ($marked[$i] == true)

            continue;

  

        $num = 2 * $i + 1;

        $num = Rotate($num); // функция вращения простого числа

  

        // теперь мы проверяем вращение этого

        // простое число, если новое вращение простое

        // проверка следующего вращения, до нового вращения

        // становится фактическим простым числом, и если

        // новое вращение, если не простое, то разрыв

        while ($num != 2 * $i + 1)

        {

            if ($num % 2 == 0) // проверка на четность

                break;

  

            // если повернутое число простое, то

            // поворот для следующего

            if ($marked[(int)(($num - 1) / 2)] == false)

                $num = Rotate($num);

            else

                break;

        }

  

        // если проверенное число является круглым

        // премьер распечатать

        if ($num == (2 * $i + 1))

            print($num." ");

    }

}

  
// Сито Сундарама для генерации простого числа

function SieveOfSundaram(&$marked, $nNew)

{

    // Основная логика сундарама. Отметьте все числа

    // формируем i + j + 2ij как true, где 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;

}

  
// Поворот функции вправо повернуть число

function Rotate($n)

{

    $rem = $n % 10; // найти номер места

    $rem *= pow(10, countDigits($n)); // разместить место

    // номер как первая цифра

    $n = (int)($n / 10); // удаляем единицу измерения

    $n += $rem; // добавить первую цифру для отдыха

    return $n;

}

  
// Функция для поиска общего количества цифр

function countDigits($n)

{

    $digit = 0;

    $n = (int)($n / 10);

    while ($n)

    {

        $digit++;

        $n = (int)($n / 10);

    }

    return $digit;

}

  
// Код драйвера

$n = 100;

circularPrime($n);

  
// Этот код предоставлен mits
?>


Выход:

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

Эта статья предоставлена Шивам Прадхан (anuj_charm) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Круговые простые числа меньше чем n

0.00 (0%) 0 votes