Рубрики

Эмирские номера

Эмирп — это слово «простое», записанное в обратном порядке, и оно относится к простому числу, которое становится новым простым числом, когда вы меняете его цифры. Эмирпы не включают палиндромные простые числа (например, 151 или 787) и однозначные простые числа, такие как 7. 107, 113, 149 и 157 — поменяйте их местами, и у вас в руках будет новое простое число. Источник: Вики

Учитывая число n, задача состоит в том, чтобы напечатать все Emrips, меньшие или равные n.
Примеры :

Input  : n = 40
Output : 13 31 

Input  : n = 100
Output : 13 31 17 71 37 73 79 97

Ниже приведены шаги:
1) Используйте сито Эратосфена, чтобы сгенерировать все простые числа, меньшие или равные n. Мы также можем использовать сито сундарам .

2) Пройдите через все сгенерированные простые числа. Для каждого пройденного простого числа выведите это число и его обратное, если выполняются следующие условия.
………… .a) Если обратное тоже простое.
………… .b) Обратное не совпадает с простым (палиндромы не допускаются)
………… .c) Реверс меньше или равен n.

Ниже приведена реализация вышеуказанной идеи.

C ++

// Программа для печати чисел эмиратов меньше n
#include <bits/stdc++.h>

using namespace std;

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

int reverse(int x)

{

    int rev = 0;

    while (x > 0)

    {

        rev = (rev*10) + x%10;

        x = x/10;

    }

    return rev;

}

  
// Ситовый метод, используемый для генерации номера эмира
// (использование сита Эратосфена)

void printEmirp(int n)

{

    // Создаем логический массив "prime [0..n]" и инициализируем

    // все записи это как правда. Значение в простом [i] будет

    // наконец, ложь, если я не простое число, иначе истина.

    bool prime[n+1];

    memset(prime, true, sizeof(prime));

  

    for (int p=2; p*p<=n; p++)

    {

        // Если простое число [p] не изменилось, то это простое число

        if (prime[p] == true)

        {

            // Обновить все кратные р

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

  

    // Обходим все простые числа

    for (int p=2; p<=n; p++)

    {

        if (prime[p])

        {

            // Найти обратное число

            int rev = reverse(p);

  

            // Число - это emrip, если это не палиндром

            // число и его обратное также простое.

            if (p != rev && rev <= n && prime[rev])

            {

               cout << p << " " << rev << " ";

  

               // Помечаем обратное простое число как ложное, чтобы оно

               // снова не печатается

               prime[rev] = false;

            }

        }

    }

}

  
// Драйвер программы

int main()

{

    int n = 40;

    printEmirp(n);

    return 0;

}

Джава

// Java-программа для печати Emirp
// числа меньше чем n

import java.util.Arrays;

  

class GFG

{

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

    static int reverse(int x)

    {

        int rev = 0;

        while (x > 0)

        {

            rev = (rev * 10) + x % 10;

            x = x / 10;

        }

        return rev;

    }

      

    // Ситовый метод, используемый для генерации номера эмира

    // (использование сита Эратосфена)

    static void printEmirp(int n)

    {

        // Создаем логический массив "prime [0..n]" и инициализируем

        // все записи это как правда. Значение в простом [i] будет

        // наконец, ложь, если я не простое число, иначе истина.

        boolean prime[]=new boolean[n + 1];

        Arrays.fill(prime,true);

      

        for (int p = 2; p * p <= n; p++)

        {

            // Если простое число [p] не изменилось, то это простое число

            if (prime[p] == true)

            {

                // Обновить все кратные р

                for (int i = p * 2; i <= n; i += p)

                    prime[i] = false;

            }

        }

      

        // Обходим все простые числа

        for (int p = 2; p <= n; p++)

        {

            if (prime[p])

            {

                // Найти обратное число

                int rev = reverse(p);

      

                // Число - это emrip, если это не палиндром

                // число и его обратное также простое.

                if (p != rev && rev <= n && prime[rev])

                {

                    System.out.print(p + " " + rev + " ");

          

                    // Помечаем обратное простое число как ложное, чтобы оно

                    // снова не печатается

                    prime[rev] = false;

                }

            }

        }

    }

      

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

    public static void main (String[] args)

    {

        int n = 100;

        printEmirp(n);

    }

}

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

python3

# Программа для печати номеров Эмирп
# меньше чем n

  
# Функция поиска реверса
№ любого числа

def reverse(x):

  

    rev = 0;

    while (x > 0):

        rev = (rev * 10) + x % 10;

        x = int(x / 10);

  

    return rev;

  
# Метод сита, используемый для генерации
# номер эмиграции (использование сита
# Эратосфен)

def printEmirp(n):

  

    # Создайте логический массив "prime [0..n]"

    # и инициализировать все записи как true.

    # Значение в простом [i], наконец, будет

    # ложь, если я не простое число, иначе верно.

    prime = [1] * (n + 1);

    p = 2;

    while (p * p <= n):

          

        # Если простое число [p] не изменилось,

        # тогда это простое

        if (prime[p] == 1):

              

            # Обновить все кратные р

            for i in range(p * 2, n + 1, p):

                prime[i] = 0;

        p += 1;

  

    # Пройдите все простые числа

    for p in range(2, n + 1):

        if (prime[p] == 1):

              

            # Найти обратный номер

            rev = reverse(p);

  

            # Число - это emrip, если это не так

            # номер палиндрома и его

            # обратное тоже простое.

            if (p != rev and rev <= n and

                       prime[rev] == 1):

                print(p, rev, end = " ");

      

                # Отметить обратное простое число как

                # ложь, так что это

                # не печатается снова

                prime[rev] = 0;

  
Код водителя

n = 100;

printEmirp(n);

  
# Этот код предоставлен mits

C #

// C # программа для печати Emirp
// числа меньше чем n

using System;

  

class GFG

{

    // Функция для поиска

    // обратный номер

    static int reverse(int x)

    {

        int rev = 0;

        while (x > 0)

        {

            rev = (rev * 10) + x % 10;

            x = x / 10;

        }

        return rev;

    }

      

    // Метод сита, используемый для

    // генерируем номер эмира

    // (использование сита Эратосфена)

    static void printEmirp(int n)

    {

        // Создать логический массив

        // "prime [0..n]" и инициализируем

        // все записи это как правда. Ценность

        // в простом [i], наконец, будет ложным

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

        bool []prime = new bool[n + 1];

        for(int i = 0; i < n + 1; i++)

        prime[i] = true;

      

      

        for (int p = 2; p * p <= n; p++)

        {

            // Если простое число [p] не изменилось,

            // тогда это простое число

            if (prime[p] == true)

            {

                // Обновить все кратные р

                for (int i = p * 2; i <= n; i += p)

                    prime[i] = false;

            }

        }

      

        // Обходим все простые числа

        for (int p = 2; p <= n; p++)

        {

            if (prime[p])

            {

                // Найти обратное число

                int rev = reverse(p);

      

                // число - это emrip, если оно

                // не число палиндрома

                // и его обратное тоже простое.

                if (p != rev && rev <= n && prime[rev])

                {

                    Console.Write(p + " " + rev + " ");

          

                    // Пометить обратное простое число как ложное

                    // чтобы он снова не печатался

                    prime[rev] = false;

                }

            }

        }

    }

      

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

    public static void Main ()

    {

        int n = 100;

        printEmirp(n);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Программа для печати номеров Эмирп
// меньше чем n

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

function reverse($x)

{

    $rev = 0;

    while ($x > 0)

    {

         $rev = ($rev  * 10) + $x % 10;

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

    }

    return $rev;

}

  
// Метод сита, используемый для генерации
// номер эмиссии (использование сита
// Эратосфен)

function printEmirp($n)

{

    // Создаем логический массив "prime [0..n]"

    // и инициализируем все записи как true.

    // Значение в простом [i] будет наконец

    // false если я не простое число, иначе true.

    $prime = array_fill(0, ($n + 1), 1);

  

    for ($p = 2; $p * $p <= $n; $p++)

    {

        // Если простое число [p] не изменилось,

        // тогда это простое число

        if ($prime[$p] == 1)

        {

            // Обновить все кратные р

            for ($i = $p * 2; $i <= $n; $i += $p)

                $prime[$i] = 0;

        }

    }

  

    // Обходим все простые числа

    for ($p = 2; $p <= $n; $p++)

    {

        if ($prime[$p] == 1)

        {

            // Найти обратное число

            $rev = reverse($p);

  

            // Число является emrip, если оно не

            // номер палиндрома и его

            // обратное тоже простое.

            if ($p != $rev && $rev <= $n && 

                $prime[$rev] == 1)

            {

                echo $p . " " . $rev . " ";

      

                // Пометить обратное простое число как

                // ложь, чтобы

                // снова не печатается

                $prime[$rev] = 0;

            }

        }

    }

}

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

$n = 100;

printEmirp($n);

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

Выход :

13 31 17 71 37 73 79 97

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

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

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

Эмирские номера

0.00 (0%) 0 votes