Обратное простое число - PullRequest
Новая
       10

Обратное простое число

0 голосов
/ 17 мая 2018

Я хочу проверить, простое ли число a и его обратное.Номер должен быть прочитан с клавиатуры.

Ограничения:

  • 1 ≤ a ≤ 2000000000
  • a не имеет последней цифры 0

Вот несколько примеров ввода для a и ожидаемого вывода 

Input  Output
5      Yes
112    No
17     Yes

Вот что я пробовал: 

#include <iostream>
using namespace std;

int main()
{
    int a;
    cin>>a;
    int RevNum =0;
    int Remain;
    int i=2;
    int prim = 1;
    int a_inainte = a;
    if ( (1 <= a && a <= 2000000000) && (a % 10 != 0) )
    {
            while(a != 0)
            {
                Remain = a % 10;
                RevNum = RevNum * 10 + Remain;
                a /= 10;
            }

            if (i < RevNum && i< a_inainte)
            {
                if (RevNum % i == 0 || a_inainte % i ==0)
                    prim = 0;
                ++i;
            }

            if (RevNum == 1 && a_inainte == 1)
                prim = 0;
            if (prim == 1)
                cout<<"DA";
            else
                cout<<"NU";
        }
        else
        {
            cout<<"NU";
        }
    return 0;
    }

Я не уверенпочему, но все в кодовых блоках вроде бы нормально, но я все еще не получаю все баллы за тест (это потому, что компилятор проверяет код с большим количеством цифр).

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

Полагаю, вы хотите проверить, является ли a или обратное к a простым числом, путем деления всех целых чисел, меньших или равных этим числам a, но в коде вы делите только на i = 2 и i = 3. Выдолжен перебрать i.

0 голосов
/ 18 мая 2018

Вы можете написать короткую функцию для проверки простоты числа.

Код ниже основан на псевдокоде из Википедии .Объяснение того, как это работает, объясняется более подробно там, но по существу, чтобы проверить, является ли число n простым, вам нужно проверить, что оно не делится на любое простое число i от 2 до sqrt(n).

bool is_prime(int n) {
    if (n <= 1)
        return false;
    else if (n <= 3)
        return true;
    else if (n % 2 == 0 || n % 3 == 0)
        return false;

    int i = 5;
    while (i*i <= n) {
         if (n % i == 0 || n % (i + 2) == 0)
             return false;
         i += 6;
    }
    return true;
}

Теперь вы можете проверить, простое ли a, просто позвонив по номеру 

is_prime(a);

Чтобы проверить, простое ли обратное, вам необходимо вычислить число равных a.Я нашел интересный подход от Arslan7041 здесь , который работает почти так же, как то, что вы уже делаете: 

int reverse(int x) {
    bool negative = false;
    if(x < 0) {
        negative = true;
        x = -x;
    }

    int reversed = 0;
    while(x > 0) {
        reversed = reversed*10 + x%10;
        x /= 10;
    }

    if(negative) reversed = -reversed;

    return reversed;
}

И теперь вы можете проверить, проста ли обратная сторона aсо следующим: 

 is_prime(reverse(a));

Наконец, мы можем решить ваши два особых ограничения с помощью простого оператора if. 

if (1 <= a && a <= 2000000000 && a % 10 != 0 
    && is_prime(a) && is_prime(reverse(a)) ) {
    cout << "DA\n";
}
...