0

Условие задачи:

Определим простой цифровой корень (ПЦК) натурального числа 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 итераций, что очень даже выполнимо. Как можно оптимизировать программу? И в чем может быть проблема?

1
  • ошибка была найдена с помощью дебаггера, однако даже так, мне не понятно что ее вызывает. ошибка в check_prime(). она проходит по всем числам до n. хотя я же написал в условии цикла i * i <= n. загадка
    – Learpcs
    Commented 8 июл. 2020 в 0:16

2 ответа 2

3

Смотрите, 2^31-1 = 0x7FFFFFFF. Что происходит для этого числа (вообще-то для любого из диапазона 2147395601-2147483647)? Когда вы проверяете

i*i <= n

сначала вычисляется произведение двух intов - в виде int.

Итак, 1, 2, 3... - i*i <= n. Добираемся до 46340 - нет, 2147395600 все еще меньше... 46341? Возводим в квадрат - 2147488281, так? Нет, не так - потому что это больше, чем можно поместить в int, так что формально это UB, а неформально - это число обрезается и превращается в -2147479015 - да, именно в отрицательное.

Затем оно преобразуется для сравнения в long long, но это не меняет его знака, и мы получаем вечный цикл...

Так что вам нужно просто - ну вот такие входные данные - исправить

for (int i = 2;

на

for (long long i = 2;

P.S. Ну, или написать что-то типа

#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();}

:)

1

Для чисел больших 2^15.5 при вычислении i * i происходит переполнение целого. Вычисляйте корень из n (один раз, до цикла) и используйте в условии цикла.

Еще. Проверяйте деление на двойку отдельно, а потом for (int i = 3; ...; i += 2).

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.