Получение слишком мало divisors

Question

Это программа для подсчета числа делителей для числа, но она дает один меньше делителя, чем на самом деле для этого числа.

#include <stdio.h> 

int i = 20; 
int divisor; 
int total; 

int main() 
{ 
    for (divisor = 1; divisor <= i; divisor++) 
    { 
     if ((i % divisor == 0) && (i != divisor)) 
     { 
      total = total++; 
     } 
    } 
    printf("%d %d\n", i, total); 
    return 0; 
} 

Число 20 имеет 6 делителей, но программа говорит, что существует 5 делителей.

Answer 1

&& (i != divisor) 

означает, что 20 не будет считаться делителем. Если вы хотите, чтобы это было рассмотрено, выровняйте этот бит кода, и вы получите весь набор, {1, 2, 4, 5, 10, 20}.

Даже если вы не хотите число подсчитанное в качестве делителя, вы могли бы еще угробить этот код и использовать только < вместо <= в for заявлении.

И:

total = total++; 

является совершенно ненужным. Это может даже быть неопределенными, я просто слишком ленив, чтобы проверить, на данный момент, и это не важно, так как никто не пишет код, как это долгое :-)

Используйте либо:

total = total + 1; 

или (лучше) :

total++; 

Answer 2

Вы добавили дополнительную проверку && (i != divisor), как описано в данном ответе.

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

// this function return the number of divisor for n. 
// if n = (m^a) (n^b) ... where m, n.. are prime factors of n 
// then number of divisor d(n) = (a+1)*(b+1).. 
int divisorcount(int n){ 

    int divider = 2; 
    int limit = n/2; 
    int divisorCount = 1; 
    int power = 0; 

    // loop through i=2...n/2 
    while(divider<=limit){ 
    if(n%divider==0){ 
     // dividing numper using prime factor 
     // (as smallest number devide a number 
     // is it's prime factor) and increase the 
     // power term for prime factor. 
    power++; 
    n/=divider; 
    } 
    else{ 
     if(power != 0){ 
     // use the prime factor count to calculate 
     // divisor count. 
     divisorCount*=(power+1); 
     } 
     power = 0; 
     divider++; 
    // if n become 1 then we have completed the 
    // prime factorization of n. 
    if(n==1){ 
     break; 
    } 

    } 
    } 
return divisorCount; 
} 

Answer 3

Подсчет делителей, возможно, проще и, конечно, быстрее, чем любой из них. Ключевой факт, который следует отметить, состоит в том, что если p - делитель n, то и n/p. Всякий раз, когда p не является квадратным корнем из n, вы получаете ДВА дивизоров на один тест деления, а не один.

int divcount(int n) 
{ 
    int i, j, count=0; 
    for (i=1, j=n; i<j; j = n/++i) 
    { 
     if (i*j == n) 
      count += 2; 
    } 
    if (i == j && i*j == n) 
     ++count; 
    return count; 
} 

Это выполняет работу с sqrt (n) делениями и умножениями sqrt (n). Я выбираю это, потому что, хотя j = n/i и еще один j% i можно сделать с инструкцией с одним делением на большинстве процессоров, я не видел, чтобы компиляторы подхватили эту оптимизацию. Поскольку умножение является одночасовым для современных настольных процессоров, тест i * j == n намного дешевле второго деления.

PS: Если вам нужен список делителей, они появляются в цикле как значения i и j, а, возможно, как значение i == j == sqrt (n) в конце, если n является квадратом ,