c - 使用for循环时，如何修复某些测试用例中的 'time limit exceeded'？

Question

我们有一系列数字，它们是从 1 到 n 的数字之和。(1,3,6,10,...)这个问题要我找到这个系列中具有 k 个约数的最小数字。

我的代码在所有测试用例上都能正常工作，但超出了时间限制。它内部有一个 while 循环和一个 for 循环。

int main()
{
        int k, sum, counter = 0, n = 1;
    scanf("%d", &k);
    while (counter != k) {
        counter = 0;
        sum = n*(n + 1) / 2;  //sum of numbers from 1 to n.(formula)
        for (int i = 1; i <= sum / 2; i++) //counts the divisors
            if (sum%i == 0)counter++;
        counter++;  //adds one to the counter because of number 1
        n++;
}
    printf("%d",sum);
    return 0;
}

And here is a example:

Input:k=4
Output:6

我应该怎样做才能拥有更快更好的程序？

Answer 1

没有找到好的副本。这是一个复杂度为 O(sqrt(n)) 的解决方案。取自https://www.geeksforgeeks.org/count-divisors-n-on13/

// function to count the divisors 
int countDivisors(int n) 
{ 
    int cnt = 0; 
    for (int i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            // If divisors are equal, 
            // count only one 
            if (n / i == i) 
                cnt++; 

            else // Otherwise count both 
                cnt = cnt + 2; 
        } 
    } 
    return cnt; 
} 

在同一个站点上，有一个运行时间复杂度为 O(n^(1/3)) 的站点，但稍微复杂一些。它适用于 C++，但只需添加 #include <stdbool.h>它应该可以工作。

void SieveOfEratosthenes(int n, bool prime[], 
                         bool primesquare[], int a[]) 
{ 
    // Create a boolean array "prime[0..n]" and initialize all entries as
    // true. A value in prime[i] will finally be false if i is  Not a prime,
    // else true. 
    for (int i = 2; i <= n; i++) 
        prime[i] = true; 

    // Create a boolean array "primesquare[0..n*n+1]" and initialize all 
    // entries it as false. A value in squareprime[i] will finally be true 
    // if i is square of prime, else false. 
    for (int i = 0; i <= (n * n + 1); i++) 
        primesquare[i] = false; 

    // 1 is not a prime number (Look it up if you doubt it) 
    prime[1] = false; 

    for (int p = 2; p * p <= n; p++) { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) { 
            // Update all multiples of p 
            for (int i = p * 2; i <= n; i += p) 
                prime[i] = false; 
        } 
    } 

    int j = 0; 
    for (int p = 2; p <= n; p++) { 
        if (prime[p]) { 
            // Storing primes in an array 
            a[j] = p; 

            // Update value in primesquare[p*p], if p is prime. 
            primesquare[p * p] = true; 
            j++; 
        } 
    } 
} 

// Function to count divisors 
int countDivisors(int n) 
{ 
    // If number is 1, then it will have only 1 
    // as a factor. So, total factors will be 1. 
    if (n == 1) 
        return 1; 

    bool prime[n + 1], primesquare[n * n + 1]; 

    int a[n]; // for storing primes upto n 

    // Calling SieveOfEratosthenes to store prime factors of n and to store
    // square of prime factors of n 
    SieveOfEratosthenes(n, prime, primesquare, a); 

    // ans will contain total number of distinct divisors 
    int ans = 1; 

    // Loop for counting factors of n 
    for (int i = 0;; i++) { 
        // a[i] is not less than cube root n 
        if (a[i] * a[i] * a[i] > n) 
            break; 

        // Calculating power of a[i] in n. 
        int cnt = 1; // cnt is power of prime a[i] in n. 
        while (n % a[i] == 0) // if a[i] is a factor of n 
        { 
            n = n / a[i]; 
            cnt = cnt + 1; // incrementing power 
        } 

        // Calculating number of divisors. If n = a^p * b^q then total
        // divisors of n are (p+1)*(q+1) 
        ans = ans * cnt; 
    } 

    // if a[i] is greater than cube root of n 

    // First case 
    if (prime[n]) 
        ans = ans * 2; 

    // Second case 
    else if (primesquare[n]) 
        ans = ans * 3; 

    // Third casse 
    else if (n != 1) 
        ans = ans * 4; 

    return ans; // Total divisors 
} 

如果以上还不够，您应该研究某种动态编程。上述两种方法都是从头开始计算每个数字。但如果您要对多个数字执行此操作，则很可能可以使用以前数字中的信息。为了让大家了解一下它是如何工作的，这里有一个计算从 2 到 n 的所有素数的算法:

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

// After running this function, prime[n] will be true iff n is a prime
void createPrimeArray(bool *prime, size_t size)
{
    prime[0] = prime[1] = false;

    for(size_t i=2; i<size; i++)
        prime[i] = true;

    for(size_t i=2; i<sqrt(size); i++) {
        size_t j=i;
        while(!prime[j])
            j++;

        for(size_t k=2*j; k<size; k+=j)
            prime[k] = false;
    }
}

int main(void)
{
    bool prime[200];
    createPrimeArray(prime, 200);
    for(int i=0; i<200; i++) {
        if(prime[i])
            printf("%d ", i);
    }
}

以上内容可能还可以进一步优化。其目的是展示如何重用信息。在 createPrimeArray 中的第二个 for 循环中第一次运行之后我们已经将所有能被 2 整除的数字标记为非素数，因此我们不必再关心这些了。