题目12：第一个拥有超过500个约数的三角形数是多少？

DetConan

python3 结果是：76576500
时间:0.970447 s

1. import time
   
2. 
   
3. start = time.clock()
   
4. def get_divisors_num(n, prime):
   
5.     num = 1
   
6.     count = 1
   
7.     while (n > 1):
   
8.         for p in prime:
   
9.             while(n % p == 0):
   
10.                 count += 1
    
11.                 n = n // p
    
12.             num *= count
    
13.             count = 1
    
14.             if n == 1:
    
15.                 break
    
16.     return num
    
17. 
    
18. 
    
19. def get_primes(number):
    
20.     # '筛法找出所有质数，并求和'
    
21.     list_primes = [True] * (number + 1)
    
22.     list_primes[0] = False
    
23.     list_primes[1] = False
    
24.     for i in range(2, number):
    
25.         if list_primes[i]:
    
26.             for j in range(i ** 2, number, i):
    
27.                 list_primes[j] = False
    
28.     list_result = []
    
29.     for k in range(2, number):
    
30.         if list_primes[k]:
    
31.             list_result.append(k)
    
32.     return list_result
    
33. 
    
34. 
    
35. prime = get_primes(100000)
    
36. n = 1
    
37. while 1:
    
38.     n += 1
    
39.     s = n * (n - 1) // 2
    
40.     if get_divisors_num(s, prime) > 500:
    
41.         break
    
42. print(s)
    
43. 
    
44. end = time.clock()
    
45. print("read:%f s" % (end - start))
    

复制代码

山有扶苏啊

1. from math import sqrt
   
2. def count(n):
   
3.     t = 0
   
4.     for i in range(1, n+1):
   
5.         t += i
   
6.     return t
   
7. 
   
8. for r in range(10000000):
   
9.     s = count(r)
   
10.     result = []
    
11.     for i in range(1, int(sqrt(s))+1):
    
12.         if s%i == 0:
    
13.             result.append(i)
    
14.     if len(result) > 250:
    
15.         print(s)
    
16.         print(len(result))
    
17.         break

复制代码

76576500

cwhsmile

1. import time
   
2. import math
   
3. import functools
   
4. 
   
5. def test1():
   
6.     num = 1
   
7.     count = 0  #约数个数
   
8.     li = []
   
9.     while len(li) < 500:
   
10.         count = 0
    
11.         li = []
    
12.         if num%2 == 0:
    
13.             sjx_num = (num+1)*(num//2)
    
14.             if sjx_num%2 == 0:
    
15.                 i = 1
    
16.                 j = 4
    
17.                 while i < j:
    
18.                     if sjx_num%i == 0:
    
19.                         j = sjx_num//i
    
20.                         li.extend([i,j])
    
21.                     i += 1
    
22.                            
    
23.             else:
    
24.                 i = 1
    
25.                 j = 4
    
26.                 while i < j:
    
27.                     if sjx_num%i == 0:
    
28.                         j = sjx_num//i
    
29.                         li.extend([i,j])
    
30.                     i += 2
    
31.                            
    
32.         else:
    
33.             sjx_num = num*(num//2) + num
    
34.             if sjx_num%2 == 0:
    
35.                 i = 1
    
36.                 j = 4
    
37.                 while i < j:
    
38.                     if sjx_num%i == 0:
    
39.                         j = sjx_num//i
    
40.                         li.extend([i,j])
    
41.                     i += 1
    
42.         
    
43.             else:
    
44.                 i = 1
    
45.                 j = 4
    
46.                 while i < j:
    
47.                     if sjx_num%i == 0:
    
48.                         j = sjx_num//i
    
49.                         li.extend([i,j])
    
50.                     i += 2
    
51.                            
    
52. 
    
53.         num += 1
    
54.         
    
55. 
    
56.    
    
57.     return sjx_num,num-1
    
58. 
    
59. start = time.perf_counter()
    
60. 
    
61. print(test1())
    
62. end = time.perf_counter()
    
63. print(end-start)
    

复制代码

永恒的蓝色梦想

None

1666194196

#include <stdio.h>
void main(){
        //高度可约的三角形数
        //三角形数数列是通过逐个加上自然数来生成的。
        //例如，第7个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。三角形数数列的前十项分别是：
        //1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
        //让我们列举出前七个三角形数的所有约数：
        //1: 1        // 3: 1,3        // 6: 1,2,3,6        //10: 1,2,5,10        //15: 1,3,5,15        //21: 1,3,7,21        //28: 1,2,4,7,14,28
        //我们可以看出，28是第一个拥有超过5个约数的三角形数。
        //第一个拥有超过500个约数的三角形数是多少？
       
        int i=1,count=0;//i:从 1循环到无穷的数，count：记录三角形数有几个因数
        long sum=0; //sum:i的和（三角形数）
        while(1){
                sum+=i;//计算出三角形数
                int j;
                for(j=1;j<=sum;j++){//从 1到 这个三角形数的循环
                        if(sum%j==0){//找能整除的数的个数（因数个数）
                                count++;//如果能整除说明是因数，count+1
                        }
                }
                printf("三角形数：%d,有%d个因数\n",sum,count);//看count到几了
               
                if(count>5){//大于5，就输出这个三角形数 ，跳出 while循环 （大于500同理）
                        printf("超过5个约数的三角形数：%d",sum);
                        break;
                }else{//count记录完上一个三角形数后，要清零记录下一个
                        count=0;
                }       
                i++;
        }
}

代号-K

发现与素数都离不开关系

1. void getApproximation(int *answer, int flag, int stop)
   
2. {
   
3.     int array[flag] = {0};
   
4.     int temp[flag] = {0};
   
5.     array[0] = 2;
   
6.     int i = 1;
   
7. 
   
8.     int j = 3;
   
9.     int k = 0;
   
10. 
    
11.     bool yes = 1;
    
12.     while(true)
    
13.     {
    
14.         if(i == flag)
    
15.         {
    
16.             break;
    
17.         }
    
18.         else
    
19.         {
    
20.             k = 0;
    
21.             while( k < i)
    
22.             {
    
23.                 if(j % array[k] == 0)
    
24.                 {
    
25.                     yes = 0;
    
26.                     break;
    
27.                 }
    
28.                 k++;
    
29.             }
    
30.             if(yes)
    
31.             {
    
32.                 array[i++] = j;
    
33.             }
    
34.         }
    
35.         j += 2;
    
36.         yes = 1;
    
37.     }
    
38. 
    
39.     j = 1;
    
40.     while(true)
    
41.     {
    
42.         j++;
    
43.         yes = 1;
    
44.         *answer = 1;
    
45.         // construct trigle
    
46.         int value = 0;
    
47.         int sum = 0;
    
48.         sum = (j*(j+1))/2;
    
49.         value = sum;
    
50.         //printf("temp:1->%d = %d\t", j, value);
    
51.         // calculate this number approximation
    
52. 
    
53.         k = 0;
    
54.         while(k < i)
    
55.         {
    
56.             // judge is union
    
57.             while(sum % array[k] == 0)
    
58.             {
    
59.                 temp[array[k]-1] += 1;
    
60.                 sum /= array[k];
    
61.                 yes = 0;
    
62.             }
    
63.             // put next prime to compare
    
64.             if(sum > array[k])
    
65.             {
    
66.                 k++;
    
67.             }else
    
68.             {
    
69.                 break;
    
70.             }
    
71.         }
    
72.         if(yes)
    
73.         {
    
74.             temp[sum-1] = 1;
    
75.         }
    
76.         for(k = 0; k < array[k]; k++)
    
77.         {
    
78.             //printf("%d\n", temp[k]);
    
79.             if(temp[k] > 0)
    
80.             {
    
81.                 *answer *= (temp[k] + 1);
    
82.             }
    
83.             temp[k] = 0;
    
84.         }
    
85.         //printf("choice:%d\n", *answer);
    
86.         //break;
    
87.         if(*answer >= stop)
    
88.         {
    
89.             printf("over:%d\n", value);
    
90.             break;
    
91.         }
    
92.     }
    
93. }
    
94. int main(int argc, char *argv[])
    
95. {
    
96.     //ElementType  ret;
    
97.     int ret;
    
98.     getApproximation(&ret, 100000, 500);
    
99.     printf("answer:%d\n", ret);
    
100.     //test();
     
101.     return 0;
     
102. }

复制代码

代号-K

想复杂了，简单的

1. void getApproximationImprove(ElementType *answer, int flag)
   
2. {
   
3.     ElementType start = 1;
   
4.     ElementType sum = 0;
   
5.     ElementType numTemp;
   
6.     int count = 0;
   
7.     while(true){
   
8.         count = 0;
   
9.         sum = start*(start+1)/2;
   
10.         for(numTemp = 1; numTemp <= (ElementType) pow(sum, 0.5);numTemp++)
    
11.         {
    
12.             if(sum % numTemp == 0) count++;
    
13.         }
    
14.         *answer = sum;
    
15.         if(2*count >= flag){
    
16.             printf("%d\t%lld\t",2*count,start);
    
17.             return;
    
18.         }
    
19.         start++;
    
20.     }
    
21. }
    
22. 
    
23. int main(int argc, char *argv[]){
    
24.     //ElementType  ret;
    
25.     ElementType ret = -1;
    
26.     getApproximationImprove(&ret,500);
    
27.     printf("answer:%lld\n", ret);
    
28.     return 0;
    
29. }

复制代码

永恒的蓝色梦想

C++ 251ms

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. 
   
5. 
   
6. int main() {
   
7.     int i, j = 1, count = 0, k;
   
8.     double root;
   
9. 
   
10.     for (i = 1;; i += ++j) {
    
11.         root = sqrt(i);
    
12.         count = 0;
    
13. 
    
14.         for (k = 2; k < root; ++k) {
    
15.             if (!(i % k)) {
    
16.                 ++count;
    
17.             }
    
18.         }
    
19. 
    
20.         if (count > (fmod(root, 1) ? 249 : 250)) {
    
21.             cout << i << endl;
    
22.             return 0;
    
23.         }
    
24.     }
    
25. }

复制代码

leon0149

76576500
0.105 s

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. int main(void) {
   
5.     int num = 1;
   
6.     int i = 2;
   
7.     int cnt = 0;
   
8. 
   
9.     clock_t start, finish;
   
10.     double duration;
    
11.     start = clock();
    
12. 
    
13.     while (cnt < 500) {
    
14.         cnt = 0;
    
15.         num += i;
    
16.         for (int j = 1; j *j <= num; ++j) {
    
17.             if (num % j == 0) {
    
18.                 if (j * j == num) {
    
19.                     cnt++;
    
20.                 } else {
    
21.                     cnt += 2;
    
22.                 }
    
23.             }
    
24.         }
    
25.         i++;
    
26.     }
    
27. 
    
28.     printf("%d\n", num);
    
29. 
    
30.     finish = clock();
    
31.     duration = (double)(finish - start)/CLOCKS_PER_SEC;
    
32.     printf("%.3f s", duration);
    
33. 
    
34.     return 0;
    
35. }

复制代码

有马_冬巳

1. '''三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是：
   
2. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
   
3. 下面我们列出前七个三角形数的约数：
   
4. 1: 1
   
5. 3: 1,3
   
6. 6: 1,2,3,6
   
7. 10: 1,2,5,10
   
8. 15: 1,3,5,15
   
9. 21: 1,3,7,21
   
10. 28: 1,2,4,7,14,28
    
11. 可以看出 28 是第一个拥有超过 5 个约数的三角形数。
    
12. 那么第一个拥有超过 500 个约数的三角形数是多少？'''
    
13. 
    
14. def trinum(num_of_divisors):
    
15.     end_num = 1
    
16.     sum = 0
    
17.     Num_of_divisors = 0
    
18. 
    
19.     while Num_of_divisors < num_of_divisors:
    
20.         Num_of_divisors = 0
    
21.         sum += end_num
    
22. 
    
23.         if math.sqrt(sum) == int(math.sqrt(sum)):
    
24.             Num_of_divisors += 1
    
25. 
    
26.         for divisors in range(1,int(math.sqrt(sum))):
    
27.             if sum % divisors == 0:
    
28.                 Num_of_divisors += 2
    
29. 
    
30.         end_num += 1
    
31. 
    
32.     print("第一个拥有超过500个约数的三角形数是: %d" %sum)
    
33.     print("一共有%d个约数" %Num_of_divisors)
    
34. 
    
35. start_trinum = time.time()
    
36. trinum(500)
    
37. time_trinum = time.time() - start_trinum
    
38. print("%f秒" %time_trinum)

复制代码

第一个拥有超过500个约数的三角形数是: 76576500
一共有576个约数
3.206136秒

gonorth

import math as m
import datetime as dt


def div():
    record = []
    count = 0
    n = 0
    while 1 :
        count += 1
        n += count
        for each in range(1, int(m.sqrt(n))+ 1):
            if n % each == 0:
                record.append(each)
        if len(record) > 250:
            print (n)
            print (count)
            break
        record = []
start = dt.datetime.now()
div()
end = dt.datetime.now()
print ("用时" , end - start)

a1351468657

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. main()
   
5. {
   
6.         int i, j = 2, k, num = 1, count = 0;
   
7.         while (1)
   
8.         {
   
9.                 num += j;
   
10.                 j++;
    
11.                 k = sqrt(num);
    
12.                 for (i = 2; i <= k; i++)
    
13.                 {
    
14.                         if (num % i == 0)
    
15.                         {
    
16.                                 if (i * i == num)
    
17.                                 {
    
18.                                         count++;
    
19.                                 }
    
20.                                 else
    
21.                                 {
    
22.                                         count += 2;
    
23.                                 }
    
24.                         }
    
25.                 }
    
26.                 if (count + 2 > 500)
    
27.                 {
    
28.                         break;
    
29.                 }
    
30.                 count = 0;
    
31.         }
    
32.         printf("第一个超过500个约数的三角数是：%d\n", num);
    
33. }

复制代码

若有错误，望大佬纠正！

卢本伟牛逼

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int count = 0;
   
5. 
   
6. int count_fact(int value)
   
7. {
   
8.         int i;
   
9.         int flag = 0;
   
10.         for(i=1;i<sqrt(value) + 1;i++)
    
11.         {
    
12.                 count += 1;
    
13.                 if (value%i==0) flag += 2;
    
14.         }
    
15.         return flag;
    
16. }
    
17. 
    
18. int count_fact2(int value)
    
19. {
    
20.         int i;
    
21.         int result = 1;
    
22.         int flag;
    
23.         if (value <= 2) return 0;
    
24.         for(i=2; i<=value; i++){
    
25.                 flag = 0;
    
26.                 count += 1;
    
27.                 while(value % i == 0){
    
28.                         flag += 1;
    
29.                         value /= i;
    
30.                 }
    
31.                 if (flag!=0){
    
32.                         result *= (flag + 1);
    
33.                 }
    
34.         }
    
35.         return (result == 1)?0:result;
    
36. }
    
37. 
    
38. int main(void)
    
39. {
    
40.         int i=1;
    
41. 
    
42.         while(count_fact2((i+1)*i/2) < 500) i++;
    
43. 
    
44.         printf("result = %d\n", (i+1)*i/2);
    
45.         printf("count = %d\n", count);
    
46. 
    
47.         return 0;
    
48. }
    
49. //count_fact result = 76576500
    
50. //count_fact count  = 54157266
    
51. 
    
52. //count_fact2 result = 76576500
    
53. //count_fact2 count  = 26736502

复制代码

番杰

1. #include<stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         unsigned int sum = 0,num = 0;
   
6.        
   
7.         for(int i = 1;;i++)
   
8.         {
   
9.                 sum += i;
   
10.                 for(int j = 1;j <= num ;j++)
    
11.                 {
    
12.                         if(num % j == 0)
    
13.                         {
    
14.                                 num++;       
    
15.                         }
    
16.                 }
    
17.                 if(num >= 500)               
    
18.                 {
    
19.                         break;                       
    
20.                 }       
    
21.         }
    
22.        
    
23.         printf("%d",sum);
    
24.        
    
25.         return 0;
    
26. }

复制代码

弈秋呜呜呜

0.2s

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         long res = 0;
   
6.         long i = 1,j,temp;
   
7.         int count = 0;
   
8.        
   
9.         while (1)
   
10.         {
    
11.                 res += i;
    
12.                 i++;
    
13.                 for(j = 1;j < res;j++)
    
14.                 {
    
15.                         temp = res/j;
    
16.                         if (temp < j)
    
17.                                 break;
    
18.                         if (temp * j == res)
    
19.                                 count += 2;
    
20.                 }
    
21.                 if (count >= 500)
    
22.                 {
    
23.                         printf("%ld\n",res);
    
24.                         return 0;
    
25.                 }
    
26.                 count = 0;
    
27.         }
    
28. }

复制代码

jerryxjr1220

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "time"
   
6. )
   
7. 
   
8. //题目：
   
9. //
   
10. //三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是：
    
11. //
    
12. //1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
    
13. //
    
14. //下面我们列出前七个三角形数的约数：
    
15. //
    
16. //1: 1
    
17. //3: 1,3
    
18. //6: 1,2,3,6
    
19. //10: 1,2,5,10
    
20. //15: 1,3,5,15
    
21. //21: 1,3,7,21
    
22. //28: 1,2,4,7,14,28
    
23. //可以看出 28 是第一个拥有超过 5 个约数的三角形数。
    
24. //
    
25. //那么第一个拥有超过 500 个约数的三角形数是多少？
    
26. 
    
27. func yueshu(a int32) int32 {
    
28.         n := make(map[int32]int32)
    
29.         for {
    
30.                 if a > 1 {
    
31.                         var i int32
    
32.                         for i = 2; i <= a; i++ {
    
33.                                 if a%i == 0 {
    
34.                                         n[i]++
    
35.                                         a /= i
    
36.                                         break
    
37.                                 }
    
38.                         }
    
39.                 } else {
    
40.                         res := int32(1)
    
41.                         for _, value := range n {
    
42.                                 res *= (value + 1)
    
43.                         }
    
44.                         return res
    
45.                 }
    
46. 
    
47.         }
    
48. }
    
49. 
    
50. func triangle(n int32) int32 {
    
51.         return (1 + n) * n / 2
    
52. }
    
53. 
    
54. func main() {
    
55.         t := time.Now()
    
56.         var i int32 = 1
    
57.         for {
    
58.                 if yueshu(triangle(i)) > 500 {
    
59.                         fmt.Println(triangle(i))
    
60.                         break
    
61.                 }
    
62.                 i++
    
63.         }
    
64.         tt := time.Now()
    
65.         fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
    
66. }

复制代码

输出：

1. GOROOT=C:\Program Files\Go #gosetup
   
2. GOPATH=C:\Users\Administrator\go #gosetup
   
3. "C:\Program Files\Go\bin\go.exe" build -o C:\Users\Administrator\AppData\Local\Temp\GoLand\___go_build_Euler12_go.exe C:\Users\Administrator\Documents\GoProject\src\Euler12.go #gosetup
   
4. C:\Users\Administrator\AppData\Local\Temp\GoLand\___go_build_Euler12_go.exe
   
5. 76576500
   
6. 耗时： 42 ms
   
7. 
   
8. 进程 已完成，退出代码为 0
   

复制代码

jerryxjr1220

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "time"
   
6. )
   
7. 
   
8. //题目：
   
9. //
   
10. //三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是：
    
11. //
    
12. //1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
    
13. //
    
14. //下面我们列出前七个三角形数的约数：
    
15. //
    
16. //1: 1
    
17. //3: 1,3
    
18. //6: 1,2,3,6
    
19. //10: 1,2,5,10
    
20. //15: 1,3,5,15
    
21. //21: 1,3,7,21
    
22. //28: 1,2,4,7,14,28
    
23. //可以看出 28 是第一个拥有超过 5 个约数的三角形数。
    
24. //
    
25. //那么第一个拥有超过 500 个约数的三角形数是多少？
    
26. 
    
27. func yueshu(a int32) int32 {
    
28.         n := make(map[int32]int32)
    
29.         for {
    
30.                 if a > 1 {
    
31.                         var i int32
    
32.                         for i = 2; i <= a; i++ {
    
33.                                 if a%i == 0 {
    
34.                                         n[i]++
    
35.                                         a /= i
    
36.                                         break
    
37.                                 }
    
38.                         }
    
39.                 } else {
    
40.                         res := int32(1)
    
41.                         for _, value := range n {
    
42.                                 res *= (value + 1)
    
43.                         }
    
44.                         return res
    
45.                 }
    
46. 
    
47.         }
    
48. }
    
49. 
    
50. func triangle(n int32) int32 {
    
51.         return (1 + n) * n / 2
    
52. }
    
53. 
    
54. func main() {
    
55.         t := time.Now()
    
56.         var i int32 = 1
    
57.         for {
    
58.                 if yueshu(triangle(i)) > 500 {
    
59.                         fmt.Println(triangle(i))
    
60.                         break
    
61.                 }
    
62.                 i++
    
63.         }
    
64.         tt := time.Now()
    
65.         fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
    
66. }

复制代码

输出：
76576500
耗时： 42 ms

Asss-whom

1. use primes::factors_uniq;
   
2. 
   
3. pub fn run() -> Result<(), Box<dyn std::error::Error>> {
   
4.     for i in 1.. {
   
5.         let num = i * (i + 1) / 2;
   
6.         let f = factor(num);
   
7.         if f > 500 {
   
8.             println!("num = {num}, factors = {f}");
   
9.             break;
   
10.         }
    
11.     }
    
12.     Ok(())
    
13. }
    
14. 
    
15. fn factor(num: u64) -> i32 {
    
16.     let f = factors_uniq(num);
    
17.     f.into_iter()
    
18.         .map(|i| {
    
19.             let mut n = num;
    
20.             let mut count = 0;
    
21.             while n % i == 0 {
    
22.                 n = n / i;
    
23.                 count += 1
    
24.             }
    
25.             count
    
26.         })
    
27.         .fold(1, |acc, x| acc * (x + 1))
    
28. }
    

复制代码

[Project Euler 12]
num = 76576500, factors = 576
[Task finished in 5ms]

TLM

## python

1. import time
   
2. tt=time.time()
   
3. # an=n(n+1)/2
   
4. # 这个算法的时间复杂度应该是O(nlog(n)),其中n是第n个数，也就是n=O(an**0.5)
   
5. # 数学能力有限，不知道和目标数据之间的联系
   
6. # 通过列表，获得所有小于等于n+1的数的约数个数
   
7. def getNlist(n):
   
8.     # 时间复杂度为O(nlog(n))这个是测试的，没计算
   
9.     nlist=[0 for i in range(n)]
   
10.     for i in range(1,int(n**0.5)+1):
    
11.         for j in range(i,n+1):
    
12.             if i*j<=n:
    
13.                 if i==j:# i为其约数
    
14.                     nlist[i*j-1]=nlist[i*j-1]+1
    
15.                 else:# i,j都是其约数
    
16.                     nlist[i*j-1]=nlist[i*j-1]+2
    
17.             else:
    
18.                 break
    
19.     return nlist
    
20. 
    
21. def getminn(nlist,mubiao):
    
22.     # O(n)
    
23.     for i in range(len(nlist)-1):
    
24.         if i%2==1:
    
25.             # an=n(n+1)/2,拆成两个n和(n+1)/2这样的结构，最大公约数为1，只有一个相同的约数
    
26.             # 排列组合形成an的约数。这是整个算法中最精髓的
    
27.             if nlist[(i+1)//2-1]*nlist[i+1]>=mubiao:
    
28.                 return False,i+1
    
29.         else:
    
30.             if nlist[i]*nlist[(i+2)//2-1]>=mubiao:
    
31.                 return False,i+1
    
32.     return True,0
    
33. # 目标值
    
34. mubiao=500
    
35. n=mubiao
    
36. data=(True,0)
    
37. while data[0]:
    
38.     nlist=getNlist(n)
    
39.     data=getminn(nlist,mubiao)
    
40.     # print(n)
    
41.     # print(nlist)
    
42.     # 找不到就放大列表，倍率放大寻找更快
    
43.     n=n*2
    
44. print(data[1])# 第几个
    
45. print(data[1]*(data[1]+1)/2)# 三角数
    
46. print(time.time()-tt)

复制代码

44ms

QLYYLQ

1. #include<stdlib.h>
   
2. #include<stdio.h>
   
3. #include<stdbool.h>
   
4. #include<time.h>
   
5. #define NUMBER 200
   
6. bool a[NUMBER]={1,1,0}/*当下标对应的数组元素为0的时候，下标是素数*/;
   
7. int b[35] = {2,0};/*储存素数*/
   
8. void sushu(bool a[], int b[])
   
9. {
   
10.     int i=2;
    
11.     int j=1;
    
12.     while(i<NUMBER)
    
13.     {
    
14.         int i1 = 2*i;
    
15.         for(;i1<NUMBER;i1+=i) a[i1]=1;
    
16.         i++;
    
17.         while(i<NUMBER && a[i]==1) i++;
    
18.         b[j]=i;
    
19.         j++;
    
20.     }
    
21. }
    
22. int sum(int i)
    
23. {
    
24.     return (i*(i+1))/2;
    
25. }
    
26. int jieda(int sum1,int b[])
    
27. {
    
28.     /*分解质因数*/
    
29.     int c[35]={0};
    
30.     for(int i=0;i<35;i++)
    
31.     {
    
32.         while(sum1%b[i]==0)
    
33.         {
    
34.             c[i]+=1;
    
35.             sum1/=b[i];
    
36.         }
    
37.     }
    
38.     /*计算因数个数*/
    
39.     int j=0;
    
40.     int answer =1;
    
41.     while(j<35)
    
42.     {
    
43.         if(c[j] != 0) answer*=(c[j]+1);
    
44.         j++;
    
45. 
    
46.     }
    
47.     return (answer);
    
48. }
    
49. int main()
    
50. {
    
51.     clock_t finish,start;
    
52.     start=clock();
    
53.     sushu(a,b);
    
54.     for(int i =100;i<20000;i++)
    
55.     {
    
56.         if(jieda(sum(i),b)>=500)
    
57.         {
    
58.             printf("%d\n",sum(i));
    
59.             break;
    
60.         }
    
61.     }
    
62.     finish=clock();
    
63.     double duration= (double)(finish - start)/CLOCKS_PER_SEC;
    
64.     printf("%.3f",duration);
    
65.     system("pause");
    
66.     return 0;
    
67. 
    
68. }
    
69. 
    

复制代码

时间是0.06s

这是用C语言写的
首先是用一个欧拉筛来筛选出来需要的素数，再通过质因数来计算因数个数
我的理解是这样的：一个数可以被分解成一连串的素数相乘，那么它的所有因数就是通过质因数不同组合后相乘得到的，比如：24=2*2*2*3，那么24的因数就是1，24； 3，8； 4，6； 2，14；其实都是2，2，2，3的不同组合，比如这里是2的三次方，那么我们就应该有四种选择（不选，选一个，选两个...）来组成一个因数，同理三也是，所以24的因数个数就是（3+1）*（1+1）=8个