Является ли число кубом простого числа C++

Question

Вот код,должен вывести Yes если N-куб простого числа

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int N;
    cin>>N;
    int k=0;
    for (int i=2;i<N/3+1;i++)
     for (int x=1;x<i;x++){
         if (i%x==0) k+=1;
         if (k == 2 and i*i*i==N) cout<<"Yes"<<endl;
         else cout<<"No"<<endl;}

    return 0;
}

Answer 1

Cледовало импортировать <iostream>, чтобы пользоваться стандарными потоками ввода-вывода.

Вложенный цикл для определения, является ли число простым, можно переписать, отбрасывая числа кратные 2 и 3, и проверяя числа по формуле 6m ± 1, как показано здесь

#include <cmath>
#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    int k = 0;
    bool f = false;
    for (int i = 1; !f && i * i * i <= N; i++) {
        bool prime = i > 1 && (i % 2 != 0 || i == 2) && (i % 3 != 0 || i == 3);
        int x = 5;
        int d = 2;
        while (prime && x * x <= i) {
            prime = i % x != 0;
            x += d;
            d = 6 - d;
        }
        f = prime && i * i * i == N;
    }
    if (f) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Тогда для входных значений 1, 64, 216 и т.п. будет выводиться No, так как найденные кубические корни не являются простыми числами.

Возможен и такой оптимизированный вариант с одним циклом, в котором будет досрочный выход, как только потенциальный корень окажется составным числом, и поэтому в цикле будет строгое условие:

bool isPrimeCube(int n) {
    bool prime = n > 1;
    int d = 1;
    int root;
    for (root = 2; prime && root * root * root < n; root += d) {
        prime = n % root != 0;
        switch (root) {
            case 2: d = 1; break;
            case 3: case 5: d = 2; break;
            default: d = 6 - d;
        }
    }
    return prime && root * root * root == n;
}

Тест:

int main() {
    int arr[] = {1, 2, 3, 4, 5, 0, 20, 27, 64, 125, 216, 512, 1000, 1331, 12167};
    for (int N : arr) {
       cout << N << " ? " << (isPrimeCube(N) ? "Yes" : "No") << endl;
    }

    return 0;
}

Результат:

1 ? No
2 ? No
3 ? No
4 ? No
5 ? No
0 ? No
20 ? No
27 ? Yes
64 ? No
125 ? Yes
216 ? No
512 ? No
1000 ? No
1331 ? Yes
12167 ? Yes

Answer 2

icbrt (integer cubic root) находит наибольшее целое, куб которого меньше или равен x. Простой перебор без оптимизаций:

int icbrt(int x) {
    int y = 0;
    // условие цикла равносильно i * i * i <= x но не вызывает
    // переполнение для x близких к верхней границе типа.
    for (int i = 1; i * i <= x / i; ++i) {
        y = i;
    }
    return y;
}

is_prime проверяет что число n простое. То есть больше единицы и не делится на числа в диапазоне [2, n). Простой перебор без оптимизаций:

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i < n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

is_cube_of_prime решает задачу - проверяет что n - куб простого числа. Извлекаем кубический корень, проверяем что его куб равен n и что он простой:

bool is_cube_of_prime(int n) {
    int m = icbrt(n);
    return m * m * m == n && is_prime(m);
}

Ввод и вывод:

int main() {
    int n;
    if (std::cin >> n) {
        std::cout << (is_cube_of_prime(n) ? "Yes" : "No") << '\n';
    }
}

P.S. Ничего не оптимизировано, потому что int обычно 32 бита. Максимальное значение куба 1290. Не долго сделать столько итераций чтобы извлечь корень и проверить его на простоту.

БЛОГ НА HUSL

Является ли число кубом простого числа C++

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