The task of finding a" simple " digital root. C++
Condition of the task:
We define the simple digital root (PCC) of a natural number N as follows. If N is a prime number, then PCC(N) = N. If the number is single-digit but not prime (i.e. 1, 4, 6, 8, or 9), then PCC(N) = 0. In other cases, PCC(N) = PCC(S(N)), where S (N) is the sum of the digits of the number N.
Input data In the input file INPUT.TXT the number N is written (1 ≤ N ≤ 231-1).
Write the output data to a file OUTPUT.TXT simple digital the root of the number N.
Please note that 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 via recursion.
#include <bits/stdc++.h>
using namespace std;
bool check_prime(long long n) //проверка на простоту
{
if (n == 1) //<-- вроде лишнее, но как без этого?
return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
int sum(long long n) //сумма цифр числа
{
int sum = 0; //вроде достаточно оптимизированно
while (n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
long long root(long long n) //простой корень
{
if (check_prime(n)) //в теории можно здесь условия оптимизировать.
return n;
else if (n < 10)
return 0;
else
return root(sum(n));
}
int main()
{
long long n;
cin >> n;
cout << root(n);
}
However, on one of the tests, my program fails - it runs for too long. In fact, I don't understand why my program is running for a long time at all. Here, in theory, there is a tail recursion and, therefore, it does not work much and for a long time. Simplicity check for the largest the numbers 2^31 - 1 need to do sqrt(2^31 - 1) ~ 2^16 = 65536 iterations, which is very feasible. How can I optimize the program? And what could be the problem?
2 answers
See, 2^31-1 = 0x7FFFFFFF. What happens for this number (actually for any of the range 2147395601-2147483647)? When you check
i*i <= n
First, the product of two ints is calculated-in the form of int.
So, 1, 2, 3... - i*i <= n. Getting to 46340-no, 2147395600 is still less... 46341? Squaring it-2147488281, right? No, it's not - because it's more than can be placed in int, so formally it's UB, and informally it's a number truncated and it turns into -2147479015-yes, it is negative.
Then it is converted for comparison to long long, but this does not change its sign, and we get an eternal cycle...
So you just need to - well, here's the input data-fix
for (int i = 2;
To
for (long long i = 2;
P.S. Well, or write something like
#include <bits/stdc++.h>
#define r return
int i,N,z;
p(){for(i=sqrt(N);i>1;)if(N%i--==0)r 0;r N>1;}
K(){r p()?N:N>9?[](){z=0;do z+=N%10;while(N/=10);N=z;}(),K():0;}
main(){std::cin >> N;std::cout << K();}
:)
For numbers larger than 2^15.5, an integer overflow occurs when calculating i * i. Calculate the root of n (once, before the loop) and use it in the loop condition.
More. Check the division by two separately, and then for (int i = 3; ...; i += 2).