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

DetConan

python3 结果是：76576500
时间:0.970447 s

import time

start = time.clock()
def get_divisors_num(n, prime):
    num = 1
    count = 1
    while (n > 1):
        for p in prime:
            while(n % p == 0):
                count += 1
                n = n // p
            num *= count
            count = 1
            if n == 1:
                break
    return num


def get_primes(number):
    # '筛法找出所有质数，并求和'
    list_primes = [True] * (number + 1)
    list_primes[0] = False
    list_primes[1] = False
    for i in range(2, number):
        if list_primes[i]:
            for j in range(i ** 2, number, i):
                list_primes[j] = False
    list_result = []
    for k in range(2, number):
        if list_primes[k]:
            list_result.append(k)
    return list_result


prime = get_primes(100000)
n = 1
while 1:
    n += 1
    s = n * (n - 1) // 2
    if get_divisors_num(s, prime) > 500:
        break
print(s)

end = time.clock()
print("read:%f s" % (end - start))

山有扶苏啊

from math import sqrt
def count(n):
    t = 0
    for i in range(1, n+1):
        t += i
    return t

for r in range(10000000):
    s = count(r)
    result = []
    for i in range(1, int(sqrt(s))+1):
        if s%i == 0:
            result.append(i)
    if len(result) > 250:
        print(s)
        print(len(result))
        break

76576500

cwhsmile

import time
import math
import functools

def test1():
    num = 1
    count = 0  #约数个数
    li = []
    while len(li) < 500:
        count = 0
        li = []
        if num%2 == 0:
            sjx_num = (num+1)*(num//2)
            if sjx_num%2 == 0:
                i = 1
                j = 4
                while i < j:
                    if sjx_num%i == 0:
                        j = sjx_num//i
                        li.extend([i,j])
                    i += 1
                            
            else:
                i = 1
                j = 4
                while i < j:
                    if sjx_num%i == 0:
                        j = sjx_num//i
                        li.extend([i,j])
                    i += 2
                            
        else:
            sjx_num = num*(num//2) + num
            if sjx_num%2 == 0:
                i = 1
                j = 4
                while i < j:
                    if sjx_num%i == 0:
                        j = sjx_num//i
                        li.extend([i,j])
                    i += 1
        
            else:
                i = 1
                j = 4
                while i < j:
                    if sjx_num%i == 0:
                        j = sjx_num//i
                        li.extend([i,j])
                    i += 2
                            

        num += 1
        

    
    return sjx_num,num-1

start = time.perf_counter()

print(test1())
end = time.perf_counter()
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

发现与素数都离不开关系

void getApproximation(int *answer, int flag, int stop)
{
    int array[flag] = {0};
    int temp[flag] = {0};
    array[0] = 2;
    int i = 1;

    int j = 3;
    int k = 0;

    bool yes = 1;
    while(true)
    {
        if(i == flag)
        {
            break;
        }
        else
        {
            k = 0;
            while( k < i)
            {
                if(j % array[k] == 0)
                {
                    yes = 0;
                    break;
                }
                k++;
            }
            if(yes)
            {
                array[i++] = j;
            }
        }
        j += 2;
        yes = 1;
    }

    j = 1;
    while(true)
    {
        j++;
        yes = 1;
        *answer = 1;
        // construct trigle
        int value = 0;
        int sum = 0;
        sum = (j*(j+1))/2;
        value = sum;
        //printf("temp:1->%d = %d\t", j, value);
        // calculate this number approximation

        k = 0;
        while(k < i)
        {
            // judge is union
            while(sum % array[k] == 0)
            {
                temp[array[k]-1] += 1;
                sum /= array[k];
                yes = 0;
            }
            // put next prime to compare
            if(sum > array[k])
            {
                k++;
            }else
            {
                break;
            }
        }
        if(yes)
        {
            temp[sum-1] = 1;
        }
        for(k = 0; k < array[k]; k++)
        {
            //printf("%d\n", temp[k]);
            if(temp[k] > 0)
            {
                *answer *= (temp[k] + 1);
            }
            temp[k] = 0;
        }
        //printf("choice:%d\n", *answer);
        //break;
        if(*answer >= stop)
        {
            printf("over:%d\n", value);
            break;
        }
    }
}
int main(int argc, char *argv[])
{
    //ElementType  ret;
    int ret;
    getApproximation(&ret, 100000, 500);
    printf("answer:%d\n", ret);
    //test();
    return 0;
}

代号-K

想复杂了，简单的

void getApproximationImprove(ElementType *answer, int flag)
{
    ElementType start = 1;
    ElementType sum = 0;
    ElementType numTemp;
    int count = 0;
    while(true){
        count = 0;
        sum = start*(start+1)/2;
        for(numTemp = 1; numTemp <= (ElementType) pow(sum, 0.5);numTemp++)
        {
            if(sum % numTemp == 0) count++;
        }
        *answer = sum;
        if(2*count >= flag){
            printf("%d\t%lld\t",2*count,start);
            return;
        }
        start++;
    }
}

int main(int argc, char *argv[]){
    //ElementType  ret;
    ElementType ret = -1;
    getApproximationImprove(&ret,500);
    printf("answer:%lld\n", ret);
    return 0;
}

永恒的蓝色梦想

C++ 251ms

#include<iostream>
#include<cmath>
using namespace std;


int main() {
    int i, j = 1, count = 0, k;
    double root;

    for (i = 1;; i += ++j) {
        root = sqrt(i);
        count = 0;

        for (k = 2; k < root; ++k) {
            if (!(i % k)) {
                ++count;
            }
        }

        if (count > (fmod(root, 1) ? 249 : 250)) {
            cout << i << endl;
            return 0;
        }
    }
}

leon0149

76576500
0.105 s

#include <stdio.h>
#include <time.h>

int main(void) {
    int num = 1;
    int i = 2;
    int cnt = 0;

    clock_t start, finish;
    double duration;
    start = clock();

    while (cnt < 500) {
        cnt = 0;
        num += i;
        for (int j = 1; j *j <= num; ++j) {
            if (num % j == 0) {
                if (j * j == num) {
                    cnt++;
                } else {
                    cnt += 2;
                }
            }
        }
        i++;
    }

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

    finish = clock();
    duration = (double)(finish - start)/CLOCKS_PER_SEC;
    printf("%.3f s", duration);

    return 0;
}

有马_冬巳

'''三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 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 个约数的三角形数是多少？'''

def trinum(num_of_divisors):
    end_num = 1
    sum = 0
    Num_of_divisors = 0

    while Num_of_divisors < num_of_divisors:
        Num_of_divisors = 0
        sum += end_num

        if math.sqrt(sum) == int(math.sqrt(sum)):
            Num_of_divisors += 1

        for divisors in range(1,int(math.sqrt(sum))):
            if sum % divisors == 0:
                Num_of_divisors += 2

        end_num += 1

    print("第一个拥有超过500个约数的三角形数是: %d" %sum)
    print("一共有%d个约数" %Num_of_divisors)

start_trinum = time.time()
trinum(500)
time_trinum = time.time() - start_trinum
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

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

main()
{
        int i, j = 2, k, num = 1, count = 0;
        while (1)
        {
                num += j;
                j++;
                k = sqrt(num);
                for (i = 2; i <= k; i++)
                {
                        if (num % i == 0)
                        {
                                if (i * i == num)
                                {
                                        count++;
                                }
                                else
                                {
                                        count += 2;
                                }
                        }
                }
                if (count + 2 > 500)
                {
                        break;
                }
                count = 0;
        }
        printf("第一个超过500个约数的三角数是：%d\n", num);
}

若有错误，望大佬纠正！

卢本伟牛逼

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

int count = 0;

int count_fact(int value)
{
        int i;
        int flag = 0;
        for(i=1;i<sqrt(value) + 1;i++)
        {
                count += 1;
                if (value%i==0) flag += 2;
        }
        return flag;
}

int count_fact2(int value)
{
        int i;
        int result = 1;
        int flag;
        if (value <= 2) return 0;
        for(i=2; i<=value; i++){
                flag = 0;
                count += 1;
                while(value % i == 0){
                        flag += 1;
                        value /= i;
                }
                if (flag!=0){
                        result *= (flag + 1);
                }
        }
        return (result == 1)?0:result;
}

int main(void)
{
        int i=1;

        while(count_fact2((i+1)*i/2) < 500) i++;

        printf("result = %d\n", (i+1)*i/2);
        printf("count = %d\n", count);

        return 0;
}
//count_fact result = 76576500
//count_fact count  = 54157266

//count_fact2 result = 76576500
//count_fact2 count  = 26736502

番杰

#include<stdio.h>

int main(void)
{
        unsigned int sum = 0,num = 0; 
        
        for(int i = 1;;i++)
        {
                sum += i;
                for(int j = 1;j <= num ;j++)
                {
                        if(num % j == 0)
                        {
                                num++;        
                        }
                }
                if(num >= 500)                
                {
                        break;                        
                }        
        }
        
        printf("%d",sum);
        
        return 0;
}

弈秋呜呜呜

0.2s

#include <stdio.h>

int main(void)
{
        long res = 0;
        long i = 1,j,temp;
        int count = 0;
        
        while (1)
        {
                res += i;
                i++;
                for(j = 1;j < res;j++)
                {
                        temp = res/j;
                        if (temp < j)
                                break;
                        if (temp * j == res)
                                count += 2;
                }
                if (count >= 500)
                {
                        printf("%ld\n",res);
                        return 0;
                }
                count = 0;
        }
}

jerryxjr1220

package main

import (
        "fmt"
        "time"
)

//题目：
//
//三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 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 个约数的三角形数是多少？

func yueshu(a int32) int32 {
        n := make(map[int32]int32)
        for {
                if a > 1 {
                        var i int32
                        for i = 2; i <= a; i++ {
                                if a%i == 0 {
                                        n[i]++
                                        a /= i
                                        break
                                }
                        }
                } else {
                        res := int32(1)
                        for _, value := range n {
                                res *= (value + 1)
                        }
                        return res
                }

        }
}

func triangle(n int32) int32 {
        return (1 + n) * n / 2
}

func main() {
        t := time.Now()
        var i int32 = 1
        for {
                if yueshu(triangle(i)) > 500 {
                        fmt.Println(triangle(i))
                        break
                }
                i++
        }
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：

GOROOT=C:\Program Files\Go #gosetup
GOPATH=C:\Users\Administrator\go #gosetup
"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
C:\Users\Administrator\AppData\Local\Temp\GoLand\___go_build_Euler12_go.exe
76576500 
耗时： 42 ms 

进程 已完成，退出代码为 0

jerryxjr1220

package main

import (
        "fmt"
        "time"
)

//题目：
//
//三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是 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 个约数的三角形数是多少？

func yueshu(a int32) int32 {
        n := make(map[int32]int32)
        for {
                if a > 1 {
                        var i int32
                        for i = 2; i <= a; i++ {
                                if a%i == 0 {
                                        n[i]++
                                        a /= i
                                        break
                                }
                        }
                } else {
                        res := int32(1)
                        for _, value := range n {
                                res *= (value + 1)
                        }
                        return res
                }

        }
}

func triangle(n int32) int32 {
        return (1 + n) * n / 2
}

func main() {
        t := time.Now()
        var i int32 = 1
        for {
                if yueshu(triangle(i)) > 500 {
                        fmt.Println(triangle(i))
                        break
                }
                i++
        }
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：
76576500
耗时： 42 ms

Asss-whom

use primes::factors_uniq;

pub fn run() -> Result<(), Box<dyn std::error::Error>> {
    for i in 1.. {
        let num = i * (i + 1) / 2;
        let f = factor(num);
        if f > 500 {
            println!("num = {num}, factors = {f}");
            break;
        }
    }
    Ok(())
}

fn factor(num: u64) -> i32 {
    let f = factors_uniq(num);
    f.into_iter()
        .map(|i| {
            let mut n = num;
            let mut count = 0;
            while n % i == 0 {
                n = n / i;
                count += 1
            }
            count
        })
        .fold(1, |acc, x| acc * (x + 1))
}

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

TLM

## python

import time
tt=time.time()
# an=n(n+1)/2
# 这个算法的时间复杂度应该是O(nlog(n)),其中n是第n个数，也就是n=O(an**0.5)
# 数学能力有限，不知道和目标数据之间的联系
# 通过列表，获得所有小于等于n+1的数的约数个数
def getNlist(n):
    # 时间复杂度为O(nlog(n))这个是测试的，没计算
    nlist=[0 for i in range(n)]
    for i in range(1,int(n**0.5)+1):
        for j in range(i,n+1):
            if i*j<=n:
                if i==j:# i为其约数
                    nlist[i*j-1]=nlist[i*j-1]+1
                else:# i,j都是其约数
                    nlist[i*j-1]=nlist[i*j-1]+2
            else:
                break
    return nlist

def getminn(nlist,mubiao):
    # O(n)
    for i in range(len(nlist)-1):
        if i%2==1:
            # an=n(n+1)/2,拆成两个n和(n+1)/2这样的结构，最大公约数为1，只有一个相同的约数
            # 排列组合形成an的约数。这是整个算法中最精髓的
            if nlist[(i+1)//2-1]*nlist[i+1]>=mubiao:
                return False,i+1
        else:
            if nlist[i]*nlist[(i+2)//2-1]>=mubiao:
                return False,i+1
    return True,0
# 目标值
mubiao=500
n=mubiao
data=(True,0)
while data[0]:
    nlist=getNlist(n)
    data=getminn(nlist,mubiao)
    # print(n)
    # print(nlist)
    # 找不到就放大列表，倍率放大寻找更快
    n=n*2
print(data[1])# 第几个
print(data[1]*(data[1]+1)/2)# 三角数
print(time.time()-tt)

44ms

QLYYLQ

#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<time.h>
#define NUMBER 200
bool a[NUMBER]={1,1,0}/*当下标对应的数组元素为0的时候，下标是素数*/;
int b[35] = {2,0};/*储存素数*/
void sushu(bool a[], int b[])
{
    int i=2;
    int j=1;
    while(i<NUMBER)
    {
        int i1 = 2*i;
        for(;i1<NUMBER;i1+=i) a[i1]=1;
        i++;
        while(i<NUMBER && a[i]==1) i++;
        b[j]=i;
        j++;
    }
}
int sum(int i)
{
    return (i*(i+1))/2;
}
int jieda(int sum1,int b[])
{
    /*分解质因数*/
    int c[35]={0};
    for(int i=0;i<35;i++)
    {
        while(sum1%b[i]==0) 
        {
            c[i]+=1;
            sum1/=b[i];
        }
    }
    /*计算因数个数*/
    int j=0;
    int answer =1;
    while(j<35)
    {
        if(c[j] != 0) answer*=(c[j]+1);
        j++;

    }
    return (answer);
}
int main()
{
    clock_t finish,start;
    start=clock();
    sushu(a,b);
    for(int i =100;i<20000;i++)
    {
        if(jieda(sum(i),b)>=500)
        {
            printf("%d\n",sum(i));
            break;
        }
    }
    finish=clock();
    double duration= (double)(finish - start)/CLOCKS_PER_SEC;
    printf("%.3f",duration);
    system("pause");
    return 0;

}

时间是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个