The statement of this exercise is identical to that of exercise P22467: “Perfect primes”. 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

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