Condition tasks :

Let’s define a simple digital root (PCR) of a natural number N as follows
way. If N is a prime number, then PCC (N) = N. If the number
unambiguous, but not simple (i.e. 1, 4, 6, 8, or 9), then PCC (N) = 0.
In other cases, PCK (N) = PCK (S (N)), where S (N) is the sum of the digits of N.

Input data The input file INPUT.TXT contains the number N (1 ≤ N ≤
231-1).

Output Write a simple digital root to the OUTPUT.TXT file
numbers N.

Please note, in “other cases” a kind of recursion is obtained. Personally, I just didn’t notice it at first. Well, noticing this, I decided to use the solution through recursion.

# include & lt; bits / stdC++. h & gt;
using namespace std;
bool check_prime (long long n) // check for simplicity
{
  if (n == 1) // & lt; - seems to be superfluous, but how without it?
    return false;
  for (int i = 2; i * i & lt; = n; i ++)
    if (n% i == 0)
      return false;
  return true;
}
int sum (long long n) // sum of digits of the number
{
  int sum = 0; // seems to be quite optimized
  while (n! = 0)
  {
    sum + = n% 10;
    n / = 10;
  }
  return sum;
}
long long root (long long n) // simple root
{
  if (check_prime (n)) // in theory, conditions can be optimized here.
    return n;
  else if (n & lt; 10)
    return 0;
  else
    return root (sum (n));
}
int main ()
{
  long long n;
  cin & gt; & gt; n;
  cout & lt; & lt; root (n);
}

However, on one of the tests my program fails – it takes too long. In fact, I do not understand at all why my program takes a long time. Here, in theory, tail recursion and, therefore, it does not work much and for a long time. A simplicity check for the largest number 2 ^ 31 - 1 needs to be sqrt (2 ^ 31 - 1) ~ 2 ^ 16 = 65536 iterations, which is very doable. How can you optimize the program? And what could be the problem?

Answer 1, authority 100%

Look, 2 ^ 31-1 = 0x7FFFFFFF. What happens for this number (actually, for any of the range 2147395601-2147483647)? When you check

i * i & lt; = n

first, the product of two int s is calculated – in the form of int .

So 1, 2, 3 … – i * i & lt; = n . We get to 46340 – no, 2147395600 is still less … 46341? Square – 2147488281, right? No, not so – because this is more than you can fit into int , so formally it’s UB, but informally – this number is truncated and turns into -2147479015 – yes, exactly in negative.

It is then converted to long long for comparison, but this does not change its sign, and we get an eternal loop …

So you just need to – well, these are the input data – fix it

for (int i = 2;

to

for (long long i = 2;

P.S. Well, or write something like

# include & lt; bits / stdC++. h & gt;
#define r return
int i, N, z;
p () {for (i = sqrt (N); i & gt; 1;) if (N% i - == 0) r 0; r N & gt; 1;}
K () {rp ()? N: N & gt; 9? [] () {Z = 0; do z + = N% 10; while (N / = 10); N = z;} (), K (): 0;}
main () {std :: cin & gt; & gt; N; std :: cout & lt; & lt; K ();}

🙂

Answer 2, authority 33%

For numbers larger than 2 ^ 15.5 , an integer overflow occurs when calculating i * i . Evaluate the root of n (once, before the loop) and use in the loop condition.

More. Check division by 2 separately, and then for (int i = 3; ...; i + = 2) .