c - 代码效率不高

Question

这是ProjectEuler中第12题的代码。它给出了正确的输出为76576500。但是花了很长时间才给出输出。你能帮我为此获得更有效的代码吗？谢谢您在评论中。 https://projecteuler.net/problem=12

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

main(){
    bool flag= true;
    int triangular_n , divisor , count , remainder , counter;
    triangular_n=1;
    counter = 2;
    while(flag){
            count = 0;
            divisor = 2;
            while(divisor<triangular_n){
                    remainder = triangular_n%divisor;
                    if(remainder==0){
                            count++;

                    }
                    divisor++;
            }
            if(count==499){
                    break;
            }
            triangular_n += counter;
            counter++;
            printf("%d\n",triangular_n);
    }

    printf("%d\n", triangular_n);

}

~

Answer 1

您可以使用一些技巧来加快速度。

n第一个三角形数字是 n*(n+1)/2 .

对于所有整数n , n和n+1是互质的。这意味着 n*(n+1) 的约数个数是除数的个数 n乘以n+1的除数个数.

对于偶数 k ， k/2 的约数个数是k的约数的一半.

因此，要计算 n 的除数个数第一个三角形数，计算 n+1 的约数，乘以n的除数个数将您从上一步中获得的值除以二。