Как исправить «превышение лимита времени» в некоторых тестовых случаях при использовании цикла for?

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;
}

И вот пример:

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);
    }
}

Вышесказанное может быть дополнительно оптимизировано. Его цель - показать, как вы можете повторно использовать информацию. После первого запуска во втором цикле for в createPrimeArray мы пометили все числа, которые делятся на 2, как не простые числа, и, таким образом, нам больше не нужно заботиться о них.