Как по заданному числу определить его 2-простоту?

105
03 августа 2019, 17:10

2-простое число

(Время: 1 сек. Память: 16 Мб Сложность: 28%) Число называется 2-простым, если являются простыми числа, составленные из цифр этого числа в возрастающем и убывающем порядках.

Требуется написать программу, которая по заданному числу определит его 2-простоту.

Входные данные
Входной файл INPUT.TXT содержит натуральное число N (10 < N < 109).

Выходные данные
В выходной файл OUTPUT.TXT выведите сообщение «Yes», если число N является 2-простым и «No» - иначе.

Вот мой код:

 #include <iostream>
    #include <string>
    #include <stdlib.h>
    using namespace std;
    int  i ,x,k, sum , n, re;
    int main()
    {
        cin >> n;
        if (n < 10) {
            re += 1;
        }
        for (int i = 2; i < n - 1; i++) {
            if (n%i == 0) {
                re += 1;
            }
        }
        string s = to_string(n);
        reverse(s.begin(), s.end());
        sum = atoi(s.c_str());
        for (int i = 2; i < sum - 1; i++) {
            if (sum % i == 0) {
                re += 1;
            }
        }
        if (re == 0) {
            cout << "Yes";
    }
    else {
        cout << "No";
    }
    return 0;
}

Пишет что неправильно. В чем ошибка?

Answer 1

У вас сам подход неверен.

Первое - вы просто обращаете порядок цифр числа, а нужно получить из вашего числа 2 других - ну, если у вас 173645, то это 134567 и 765431 ("числа, составленные из цифр этого числа в возрастающем и убывающем порядках").

Во-вторых, выполняя полный цикл при проверке на простоту, вы точно вылетите за пределы отпущенного времени. Достаточно проверки на делимость до квадратного корня из n...

Если вы хотите работать через строку - то получить два нужных числа можно

string s = to_string(n);
sort(s.begin(), s.end());
int n1 = stoi(s);
reverse(s.begin(), s.end());
int n2 = stoi(s);

Ну, а проверку на простоту я бы делал примерно так

bool isPrime(int n)
{
    if (n%2 == 0) return false;
    for(int i = 3; i*i <= n; i+=2)
        if (n%i==0) return false;
    return true;
}
READ ALSO
Базовый класс Array и производные классы SortArray и XorArray

Базовый класс Array и производные классы SortArray и XorArray

Помогите закончить программу пожалуйстаНеобходимо создать базовый класс Array с виртуальными методами сложения и поэлементной обработки...

130
Что означает знак &ldquo;&amp;&rdquo; в этой строке?

Что означает знак “&” в этой строке?

Что означает знак "&" в этой строке?

140
Разбить файлы на архивы

Разбить файлы на архивы

Необходимо разбить большое количество файлов на архивыНо неизвестно, сколько их может быть

121