Псевдопростое число

Question

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

Пример: 10 - YES 9 - NO

#include <math.h>
#include <iostream>
using namespace std;

bool prost(int num)
{

    for (long long i = 2; i * i <= num; i++)
        if (num % i == 0) {
            return  false;
            break;
        }
    return true;
}


int main()
{
    int n, op, num,del=0,p;

    cin >> n;
    for (int i = 2; i < n; i++)
    {
        if ((prost(i) == true) && (n % i == 0))

            del = i;
            break;
    }
    if (prost(del)==true) cout << "YES";
    else cout << "NO";


}

Answer 1

    if (prost(i) && (n % i == 0) && prost(n / i) && (i != n / i)) {
      cout << "YES";
      return 0;
    }

Answer 2

Замените

if ((prost(i) == true) && (n % i == 0))
        del = i;
        break;

на

if ((prost(i) == true) && (n % i == 0))
{
        del = n/i;
        break;
}

а то вы проверяете опять первый делитель, и добавьте проверку, что del != i (разные простые делители).

В целом, я бы делал так...

bool pseudo_prime(int n)
{
    int d[3] = {0};
    int idx = 0;
    if (n < 4) return false;
    if (n%4 == 0) return false;
    if (n%2 == 0) { d[idx++] = 2; n/= 2; }
    for(int i = 3; i*i <= n; i += 2)
    {
        while(n%i == 0)
        {
            d[idx++] = i;
            n /= i;
            if (idx == 2) break;
        }
        if (idx == 2) break;
    }
    if (n > 1) d[idx++];
    if (idx != 2) return false;
    return (d[0] != d[1]);
}

int main()
{
    int n;
    cin >> n;
    cout << (pseudo_prime(n) ? "YES\n" : "NO\n");
}

Answer 3

Ошибка в проверках на простоту: prost(i) и prost(del) проверяют один и тот же делитель из-за присвоения del = i;. Второй делитель не проверяется совсем.

Но это вам уже сказали в других ответах. Я про другое. Возьмём функцию prost и переделаем её так, чтобы она возвращала найденный делитель. Если делителя не будет, функция вернёт само число. Функция названа min_prost_del, потому что она пытается вернуть минимальный простой делитель числа num. Это у неё всегда получается если num больше единицы: если делитель i отыщется, то он окажется простым (потому что самый маленький делитель всегда простой). Если делитель не найдётся, само число простое, его и возвращаем:

int min_prost_del(int num)
{
    for (long long i = 2; i * i <= num; i++)
        if (num % i == 0)
            return (int)i;
    return num;
}

Кроме этой функции нам ничего не нужно, только аккуратно описать логику. Читайте комментарии в функции:

bool psevdo_prost(int num)
{
    // если num меньше двух, оно точно не псевдопростое
    if (num < 2)
        return false;

    int p1 = min_prost_del(num);
    // если num простое, оно не псевдопростое
    if (p1 == num)
        return false;

    int d2 = num / p1; // получаем второй делитель

    // если второй делитель равен первому, num не псевдопростое
    if (d2 == p1) 
        return false;
    
    int p2 = min_prost_del(d2);

    // если второй делитель простой, num псевдопростое
    return p2 == d2;
}

main становится очень простым (но не псевдопростым):

int main()
{
    int n;
    std::cin >> n;
    if (psevdo_prost(n))
        std::cout << "YES\n";
    else
        std::cout << "NO\n";
}

БЛОГ НА HUSL

Псевдопростое число

Ответы (3 шт):