Условие задачи:
Определим простой цифровой корень (ПЦК) натурального числа N следующим образом. Если N - простое число, то ПЦК(N) = N. Если число однозначное, но не простое (то есть 1, 4, 6, 8 или 9), то ПЦК(N) = 0. В остальных случаях ПЦК(N) = ПЦК(S(N)), где S(N) - сумма цифр числа N.
Входные данные Во входном файле INPUT.TXT записано число N (1 ≤ N ≤ 231-1).
Выходные данные Запишите в файл OUTPUT.TXT простой цифровой корень числа N.
Прошу заметить, в "остальных случаях" получается своего рода рекурсия. Лично я просто сначала не заметил этого. Ну и заметя это, я и решил использовать решение через рекурсию.
#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);
}
Однако, на одном из тестов моя программа проваливается - слишком долго работает. На деле, я вообще не понимаю, почему моя программа работает долго. Здесь, по идее, хвостовая рекурсия и, следовательно, она не сильно и долго работает. Проверка простоты для самого большого числа 2^31 - 1
надо сделать sqrt(2^31 - 1) ~ 2^16 = 65536
итераций, что очень даже выполнимо. Как можно оптимизировать программу? И в чем может быть проблема?
check_prime()
. она проходит по всем числам до n. хотя я же написал в условии циклаi * i <= n
. загадка