Home c++ The task of finding a "simple" digital root. C++

# The task of finding a “simple” digital root. C++

Author

Date

Category

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) `.

# Programmers, Start Your Engines!

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.