Perfect primes (hard version) P43557


Statement
 

pdf   zip   main.cc   main.c   main.java   main.py

thehtml

The statement of this exercise is identical to that of exercise ‍. But here the solution required is more efficient in general.



Given a natural number n, let s(n) be the sum of the digits of n. In this exercise, we say that n is a perfect prime if the infinite sequence n, s(n), s(s(n)), …only contains prime numbers. For instance, 977 is a perfect prime, because 977, 9 + 7 + 7 = 23, 2 + 3 = 5, 5, …, are all prime numbers.

Write a recursive function that tells if a natural number n is a perfect prime or not.

Interface

C++
bool is_perfect_prime(int n);
C
int is_perfect_prime(int n);
Java
public static boolean isPerfectPrime(int n);
Python
is_perfect_prime(n) # returns bool
 
is_perfect_prime(n: int) -> bool

Precondition

We have n ≥ 0.

Observation You only need to submit the required procedure; your main program will be ignored.

Public test cases

  • Input/Output

    is_perfect_prime(977) → true
    is_perfect_prime(978) → false
    is_perfect_prime(0) → false
    is_perfect_prime(11) → true
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C C++ Java Python
    User solutions
    C++ Java Python