Проблема в правильном алгоритме делителя

Question

Я написал два алгоритма, чтобы получить сумму правильных делителей заданного числа, чтобы найти идеальное число или обильное число.

long sum_divisors_1(int a)
{
    int i, t;
    long sum = 1;
    for (i = 2, t = sqrt(a); i < t + 1; i++) {
        if (a % i == 0) {
            sum += i;
            sum += a / i;
        }
    }
    if (a % t == 0)
    sum -= t;
    return sum;
}

long sum_divisors_2(int a)
{
    int i, sum;
    sum = 0;
    for (i = 1; i < (int) (a / 2 + 1); i++) {
        if (a % i == 0)
            sum += i;
    }
    return sum;
}

И я думаю, что они оба верны, и первый из них быстрее,Но я могу получить правильный результат только из второго алгоритма.Другие части кода такие же.

Есть предложения?И как найти правильные делители в реальном промышленном программировании?

Заранее спасибо.

Answer 1

Ваша проблема лежит здесь:

if (a % t == 0)
    sum -= t;

Поскольку вы приводите t к int из числа с плавающей запятой, оно округляется до целочисленного значения. Это также предполагает , что t является фактическим квадратным корнем, когда это не так. Это будет иметь значение true, когда число имеет коэффициенты x & x+1 (модульный тест, который я также опубликовал, не будет выполнен, когда i = 6, потому что его квадратный корень равен 2,45, а коэффициент 2).

Чек действительно должен быть:

if (t*t == a)
    sum -= t;

Answer 2

Это старый вопрос, но я просматривал.

Существует гораздо более быстрый алгоритм для нахождения суммы правильных делителей.

Найдите главные факторы числа, используя Сито Эратосфена (или Аткина). При факторизации колес первые 1м простые числа займут, возможно, 30 мс.

Тогда сумма всех делителей равна

For each n

    sum += (n ^ (m+1) - 1) / (n-1)

где n - коэффициент, m - степень этого фактора.

Например, 220 2 ^ 2 5 11 являются факторами

Так что это сумма

2 ^ (2+1) - 1 / 1 *
5 ^ (1+1) - 1 / 4 *
11 ^ (1+1) - 1 / 10  
= 7 * 6 * 12
= 504

Это сумма ВСЕХ делителей, поэтому просто вычтите N

504-220 = 284

Это должно быть намного быстрее, чем пробовать все числа, особенно если вы пересчитаете сито и повторно его используете.

Answer 3

Templatetypedef решил вашу проблему; однако самый быстрый способ вычислить простые факторы - это предварительно вычислить все простые факторы вплоть до sqrt (MAX_INT) с помощью сита Eratostene, сохранить его в массив и затем использовать его для разложения числа a. Это действительно очень быстро.

Answer 4

Вот простой модульный тест, который я написал на C #, который быстро сделает недействительным # 1, если # 2 верен:

for(int i = 4; i < 28124; i++)
{
    Assert.AreEqual(sum_divisors_2(i), sum_divisors_1(i), "Failed when i = {0}", i);
}

Слишком большой комментарий ...