-1

我们有一系列数字，它们是从 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;
}

这是一个例子：

Input:k=4
Output:6

我应该怎么做才能有一个更快更好的程序？

4

1 回答 1

0

没找到好的dup。这是一个复杂度为 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);
    }
}

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

于 2019-10-30T12:56:33.317 回答