Проверьте, является ли число идеальным простым рекурсивно c ++ - PullRequest
Новая
       20

Проверьте, является ли число идеальным простым рекурсивно c ++

0 голосов
/ 10 октября 2018

Мне поручили написать программу, которая проверяет, является ли число идеальным простым или нет (сумма его цифр проста, сумма суммы его цифр проста ...).Я наткнулся на два крайних случая, которые нарушают мою программу: 

INPUT: 20328307  OUTPUT: true (expected false)
INPUT: 587899597 OUTPUT: true (expected false)

Код: 

#include <iostream>
using namespace std;


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

int sum_of_digits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

bool is_perfect_prime(int n) {
    if (sum_of_digits(n) >= 10) is_perfect_prime(sum_of_digits(n)); //cas recursiu
    return is_prime(n); //cas base

}

int main() {
    int n;
    while (cin >> n) cout << (is_perfect_prime(n) ? "true" : "false") << endl;
}

Я не вижу, где происходит сбой этого скрипта для этих двух значений и почемуэто не терпит неудачу для меньших чисел.

Ответы [ 2 ]

0 голосов
/ 10 октября 2018

Наконец-то у меня все получилось.Проблема была в цикле is_prime () for и в рекурсивном случае is_perfect_prime ().Вот что я придумал: 

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

int sum_of_digits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

bool is_perfect_prime(int n) {
    if (n < 10) return is_prime(n);
    if (! is_prime(n)) return false;
    return is_perfect_prime(sum_of_digits(n));
}

Спасибо за ваши ответы.

0 голосов
/ 10 октября 2018

Прежде всего, ваш цикл for неправильный, он должен быть вместо: 

 for (int i = 3; i * i <= n; i += 2) {
     if (n % i == 0) return false;
 }

в противном случае вы вернете true почти для каждого не четного числа.Во-вторых, вы игнорируете результат рекурсивного вызова, возможное решение: 

bool is_perfect_prime(int n) {
    if ( n >= 10 and not is_perfect_prime(sum_of_digits(n)) )
        return false;
    return is_prime(n); //cas base
}
...