c - 我怎样才能让这个程序更快？

Question

作业是编写一个程序，读取整数 k，并打印出正整数的个数 1 到 100000(含)之间，恰好有 k 个约数。例如，数字 24 有 8 个约数: 1、2、3、4、6、8、12 和 24。

我有一个正在运行的程序，但是我是否可以使搜索更快？

#include <stdio.h>
#include <math.h>


int main(void)
{   int a; //user input//
    int divisors; //running total of number of divisors//
    int sum; //running total of numbers with the required number of divisors//

    printf("Enter the target number of divisors:");
    scanf("%d", &a);
    printf("\n");

    int i;
    for (i=1; i<=100000; i++)
    {
            divisors=2;
            int p;
            for(p=2; p<i; p++)
            {if (i%p==0)
            divisors++;}

        if (divisors==a)  
        sum++;}

    printf("There are %d numbers between 1 and 100000 inclusive which have exactly %d divisors.", sum, a);

return 0;
}

Answer 1

示例代码。移动了 i 和 p 的声明以与旧的 C 类型编译器兼容(我正在使用 Microsoft/Visual Studio)。使用 ceil(sqrt(i)) 外循环。该代码处理输入 1(只有数字 1 有 1 个除数)。输入2将输出小于100,000的素数个数(小于100,000的素数有9592个)。

此方法需要迭代超过 2100 万次。迭代次数 ~= .67 n sqrt(n)。

#include <stdio.h>

int main(void)
{
    int a;          /* user input */
    int divisors;   /* total number of divisors */
    int sum;        /* count of numbers with required number of divisors */
    int i;          /* moved here for C compiler */
    int p;          /* moved here for C compiler */ 
    int sqrti;      /* ceil(sqrt(i)) */

    printf("Enter the target number of divisors: ");
    scanf("%d", &a);
    printf("\n");
    sum = 0;                            /* init sum */
    sqrti = 1;                          /* init sqrti */
    for (i = 1; i <= 100000; i++)
    {
        divisors = 0;                   /* init number of divisors */
        if(sqrti*sqrti < i)             /* update sqrti as needed */
            sqrti += 1;
        for(p = 1; p < sqrti; p++)
            if(i%p == 0)                /* if p is a divisor, count it and i/p */
                divisors += 2;
        if(p*p == i)                    /* if p*p == i, count it */
            divisors += 1;
        if (divisors == a)              /* if i has a divisors, increment sum */
            sum += 1;
    }
    printf("There are %d numbers from 1 to 100000 inclusive which have exactly %d divisors.\n", sum, a);
    return 0;
}

如果可以使用类似于素数筛法的数组，则此方法需要超过 100 万次迭代。迭代次数 ~= n ln(n)。

#include <stdio.h>
#define n 100000
int main(void)
{
int * cnt = (int *)calloc(n+1, sizeof(int));
int d;
    printf("Enter the target number of divisors: ");
    scanf("%d", &d);
    /* time complexity O(n log(n)) */
    {
    int i, j;
        for (i = 1; i <= n; i++) {
            for(j = i; j <= n; j += i) {
                cnt[j]++;
            }
        }
    }
    {
    int i;
    int sum = 0;
        for (i = 1; i <= n; i++)
            sum += (cnt[i] == d) ? 1 : 0;
        printf("excactly %d numbers have %d divisors\n", sum, d); 
    }
    free(cnt);
    return 0;
}