Найти количество делителей для числа и суммы чисел


  1. Эта функция вычисляет и возвращает количество делителей целого имеет. Но это очень медленно и я верю, что он может быть оптимизирован по скорости.

    unsigned long long int find_no_of_divisors(unsigned long long int myno,FILE *ifp)
    {
    
        unsigned long long int divsrs = 2;    
        unsigned long long int k = 2;
    
        if(myno == 1)
        {
            return 1;
        }
    
        if(myno == 2)
        {
            return 2;
        }
    
        while(1)
        {
            if((myno % k) == 0)
            {           
                divsrs++;
                if(divsrs == MY_ULLONG_MAX)
                {
                    printf("Overflow detected in the calculated value for divisors of a number... Exiting");
                    fclose(ifp);
                    exit(-1);
                }           
            }
    
            k++;        
    
            if(k > (myno/2))
            {
                break;
            }
        }
    
        return divsrs;
    }
    
  2. Это один вычисляет и возвращает сумму первых п целых чисел:

    unsigned long long int next_no(unsigned long long int idx,unsigned long long int cur_no,FILE *ifp)
    {
        unsigned long long int next_no;
    
        next_no = ((idx)*(idx + 1))/2;
    
        if((next_no - idx) != cur_no)
        {
            printf("Overflow detected in the value of the calculated number... Exiting");
            fclose(ifp);
            exit(-1);
        }
        return next_no;
    }
    

Могут ли быть какие-либо глюки или проблемы с функциональностью? (ПС - я не хочу использовать функция sqrt() функция из-за своей переносимости ограничений.)



Комментарии
2 ответа

Первая функция может быть ускорено просто пробегая до корень(myno) и добавить 2 вместо 1 в divsrs когда к делит myno , если к представляет собой квадратный корень из myno (в этом случае вы бы только добавить 1).

Вторая функция уже берет постоянно, но вы можете избавиться от умножения и деления, просто возвращаясь cur_no + индекс и используя cur_no < ULLONG_MAX ключа - IDx проверить, действительно ли там будет переполнение.


Теперь пару стиль заметки на код:

В первую очередь, кажется странным для меня, чтобы передать дескриптор файла для функции, если они на самом деле не писать (или читать из) файл. Я вижу, что вы сделали, чтобы вы могли закрыть файл перед завершением работы программы, в случае переполнения. Я бы рекомендовал, что вы возвращаете значение ошибки, когда происходит переполнение, а затем закрыть файл и выйти в вызывающем коде.

Дальнейшее твое время(1) петля в find_no_of_divisors на самом деле довольно простой дляцикла и должны быть написаны как одна. Нет необходимости в сложных потоков управления Для что-то настолько простое.

И наконец, я бы не советовал падать (некоторые) гласные из имен переменных, как вы делаете в divsrs - что как раз и приводит к опечаткам.

4
ответ дан 12 мая 2011 в 12:05 Источник Поделиться

Дополнительная отличным ответа sepp2k по математике, которые могут помочь вам:

Если у вас есть простые множители числа, вы просто берете показателей, растет с каждым один на один и принять товар.

E.g. 12 = 2^2 * 3^1 -> [2,1] -(+1)-> [3,2] -> 6
12 has 6 divisors: 1,2,3,4,6,12

E.g. 100 = 2^2 * 5^2 -> [2,2] -(+1)-> [3,3] -> 9
100 has 9 divisors: 1,2,4,5,10,20,25,50,100

Наименьший делитель числа (больше 1) не всегда простое. Алгоритм в псевдокоде выглядит так (непроверенных):

divisors(N) {
result = 1
for (p = 2; p <= sqrt(N); p++) { //check all divisors
if (n mod p == 0) {
for(f = 0; n mod p == 0; n = n / p) { //try to divide as often as possible
f++ //count how often we divide
}
result = result * (f+1)
}
}
if (N == 1) return result //number completely factored
else return 2 //then we found no factor -> N itself is prime
}

2
ответ дан 12 мая 2011 в 08:05 Источник Поделиться