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

欧拉计划

Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

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
We can see that  28  is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

题目：

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

翅膀团

#include <stdio.h>

int main(void)
{
    int a=0,i=0,j,n=1;
    while(i != 500)
    {
        i=0;
        a += n;
        for(j=1;j<=a;j++)
        {
        if(!(a % j))
        {
        i++;
        }
        }
        n++;
    }
    printf("第一个拥有超过 500 个约数的三角形数是%d\n",a);
}

如果有错误希望指出

严重超时了，电脑跑不出来

ppsuc_wuj

游客 112.80.78.x 发表于 2015-12-2 15:41
严重超时了，电脑跑不出来

那样的确效率太低，这个差不多是效率最高的 求约数个数的方法
int main()
{
    int i=1,j=2,total=1,t;
    while(total<=500)
    {
        i+=j;
        j++;
        total=1;
        for(t=1;t*t<=i;t++)
        {
            if(i%t==0)
            {
                if(i==t*t)
                    total++;
                else
                    total+=2;
            }
        }
    }
    printf("%d\n",i);
   
}

答案 76576500

huomqh

def g(x):
    i=1
    n=0
    while i**2<=x:
        if x%i==0:n+=2
        i+=1
    if (i-1)**2==x:n-=1
        
    return n

i=0
x=0
while g(x)<=500:
    i+=1
    x+=i
print (x)
    

76576500

愤怒的大头菇

import math
count = 0
total = 0
list1 = []

while True:
      count += 1
      total += count
      
      for each in range(1,int(math.sqrt(total))+1):
            if total % each == 0:
                  list1.append(each)
                  
      if len(list1) > 250:    #列表里的约数的个数是总约数的一半
            print(len(list1))
            print(total)
            break
      list1 = []              

10多秒出结果

Plusenxue

from math import *
def fun(x):
    return (1+x)*x//2
num = 1


def fun2(x):
    n = 0
    for i in range(1,floor(sqrt(x))+1):
        if x%i == 0:
            n += 1
    if floor(sqrt(x)) == sqrt(x):
        return 2*n-1
    else:
        return 2*n

k = fun2(fun(num))

while k<=500:
    num += 1
    k = fun2(fun(num))

print(fun(num))

jerryxjr1220

length:576 76576500
[Finished in 25.7s]

# 第一个拥有超过500个约数的三角形数是多少？

def yueshu(num):
        yue = []
        for i in range(1, int(num ** 0.5 + 1)):
                if num % i == 0:
                        yue.append (i)
                        yue.append (num // i)
        yue = set (yue)
        length = len (yue)
        return [yue,length]

snlist = []
suml = 0
for i in range(50000):
        suml += i
        snlist.append (suml)

for each in snlist:
        output = yueshu(each)
        lensum = output[1]
        if lensum >500:
                yuesum = list(output[0])
                fin = each
                break
        else:
                pass

print (yuesum, 'length:%d' % lensum, fin)

776667

def euler(x):
    n = 1
    tri_number = 0
    while True:
        list_a = []
        tri_number += n
        for i in range(1,int(tri_number**0.5)+1):
            if not tri_number%i:
                list_a.append(i)
            if len(list_a) > x/2:
                return tri_number
        n += 1

if __name__ == '__main__':
    print(euler(500))

lyciam

import math
import time
t = time.clock()
def euler12(count=500):
    """
    三角形数序列是由对自然数的连加构造而成的，所以第七个三角形数是1+2+3+4+5+6+7=28
    28的约数有 1,2,4,7,14,28。第一个拥有超过5个约数的三角形数是28
    第一个拥有超过500个约数的三角形数是多少
    """
    n=0
    trinum=0
    while True:
        n += 1
        trinum += n
        temp = [num for num in range(1,int(math.sqrt(trinum))+1) if trinum%num==0]
        if len(temp)>count/2: break
    numlist = [int(trinum/num) for num in temp]
    numlist.extend(temp)
    return trinum,len(numlist),sorted(numlist)

f = euler12(500)
print('{}\n\nresult:{}    count:{}    time:{}'.format(f[2],f[0],f[1],time.clock()-t) )

result:76576500    count:576    time:5.11109289657992

芒果加黄桃

# encoding:utf-8
from math import sqrt
from time import time

def getTriNumber(N=10000):
    return int((1 + N) * N / 2)
# 拆分素数因子
def findPrimeFactors(n, l_pr):
    if isPrime(n):
        return [n]
    sqr_n = int(sqrt(n)) + 1
    result = list()
    for pr in l_pr:
        if n % pr == 0:
            result.append(pr)
            result.extend(findPrimeFactors(int(n / pr), l_pr))
            break
        if pr > sqr_n:
            break
    return result
#找小于N的所有质数 学习了其他同学的代码
def getPrime(n):
        primes = [True]*n
        primes[0],primes[1]=False,False
        for (i, prime) in enumerate(primes):
            if prime:
                for j in range(i*i,n,i): 
                    primes[j] = False
        return [k for (k,trueprime) in enumerate(primes) if trueprime]    
def isPrime(n):
    if not isinstance(n, int):
        print('输入有误！')
        return
    if n < 4:
        return True;
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(3, int(sqrt(n)) + 1, 2):
        if not n % i:
            return False
    return True

start = time()            
l_pr = getPrime(10000)
num = 1
while True:
    num_fac = 1
    N = getTriNumber(num)
    fac_list = findPrimeFactors(N,l_pr)
    fac_set = set(fac_list)
    for each in fac_set:
        num_fac *= (fac_list.count(each) + 1)
    if num_fac >= 500:
        print('最小的超过500个约数的三角数是: %d, 约数个数为 %d。' % (N,num_fac))
        break
    num +=1
print('cost %.3f sec' % (time() - start))

最小的超过500个约数的三角数是: 76576500, 约数个数为 576。
cost 0.444 sec

渡风

此代码使用matlab编程
Problem12所用时间为9.8363秒
Problem12的答案为76576500

%题目12：第一个拥有超过500个约数的三角形数是多少？
 function Output=Problem12(Input)
if nargin==0
  Input=500;
 end
tic
N=1;
Num=0;
Start=sum(1:N);
while (Num<=Input)    
     N=N+1;
     Start=sum(1:N);
     Num=Factor_Num(Start);
end
Output=Start;    
toc
disp('此代码使用matlab编程')
disp(['Problem12所用时间为',num2str(toc),'秒'])
disp(['Problem12的答案为',num2str(Output)])
 end
%end
%% 子函数
%输入一个数得到一个数的所有因子的数量。
function Output=Factor_Num(Input)
if nargin==0
    Input=10000;
end
if Input==1
    Output=1;
else
    Rank=[];
    Node=floor(sqrt(Input));
    if Node*Node==Input
        Rank=Node;
        Cut=Node-1;
    else
        Cut=Node;
    end
    for ii=Cut:-1:2
        if mod(Input,ii)==0
            Temp=[ii,Rank,Input/ii];
            Rank=Temp;
        end
    end
    Output=length(Rank)+1;
end
end

FlySelf

import time

def triangular_1():
    '寻找第一个拥有超过500个约数的三角形数，不推荐'
    triangle = 1
    i = 1
    count = 0
    while count <= 500:
        count = 0
        triangle = int((i + 1) * i / 2)
        i += 1
        if triangle % 2 == 0:
            for j in range(1, int(triangle / 2)):
                if triangle % j == 0:
                    count += 1
        else:
            for j in range(1, int(triangle / 3 + 1), 2):
                if triangle % j == 0:
                    count += 1
        print('%d-->%d' %(triangle, count))
    return triangle

def find_primes(number):
    '筛法找出number个质数'
    list_primes = [True] * (number * 8)
    list_primes[0] = False
    list_primes[1] = False
    list_result = []
    while len(list_result) < number:
        for i in range(2, len(list_primes)):
            if list_primes[i]:
                for j in range(i ** 2, len(list_primes), i):
                    list_primes[j] = False
        list_result.clear()
        for k in range(2, len(list_primes)):
            if list_primes[k]:
                list_result.append(k)
        list_primes.extend([True] * number)
    return list_result[:number]

def triangular_2():
    '使用约数个数定理计算'
    list_primes = find_primes(498)
    list_exp = []
    triangle = 1
    result = 1
    i = 2
    while result <= 500:
    #while i < 7:
        triangle = int((i + 1) * i / 2)
        i += 1
        list_exp.clear()
        result = 1
        for each in list_primes:
            if each > triangle:
                break
            count = 0
            temp = triangle
            while temp % each == 0:
                temp /= each
                count += 1
            if count != 0:
                list_exp.append(count)
        for each in list_exp:
            result *= (each + 1)
    return [triangle, result]

start = time.clock()
print(triangular_2())
end = time.clock()
print('程序执行了%fs。' %(end - start))

执行结果：
[76576500, 576]
程序执行了1.046565s。

99592938

num =a=count=0
while count<=500:
    a+=1
    num+=a
    count=0
    for i in range(1,int(num**0.5)+1):
        if not num%i:
            if num==i**2:
                count+=1
            else:count+=2
print(num)

>>>
76576500

JonTargaryen

约数个数分解定理
http://baike.baidu.com/item/%E7% ... 90%86?sefr=enterbtn

#include <stdio.h>

int divi_num(int result);

int main(void)
{
    int result = 0;
    int num = 0;
    int count = 0;
    int i, temp;

    while(count <= 500)
    {
        num++;
        result += num;

        count = divi_num(result);
    }

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

    return 0;
}

int divi_num(int result)
{
    int count = 1;
    int factor_count;
    int i;

    for(i = 2; i <= result; i++)
    {
        factor_count = 0;

        while(!(result % i))
        {
            factor_count++;

            result /= i;
        }

        count *= factor_count + 1;
    }

    return count;
}

天之南

#include<stdio.h>

int count_divisor(int num);
int main()
{
        int t_num = 1;
        for (int i = 2;count_divisor(t_num)<=500;i++)
        {
                t_num += i;
        }
        printf("%d\n", t_num);
        return 0;
}

int count_divisor(int x) 
{
        int count = 0;
        int i;
        for (i = 1;i*i < x;i++)
        {
                if (x%i == 0)
                {
                        count++;
                }
        }
        count *= 2;
        if (i*i == x) count++;
        return count;
}

BngThea

def check(n,t):
    count = 2
    for i in range(2,n//2 + 1):
        if not (n % i):
            count += 1
            if count == t:
                break
    if count != t:
        return False
    return True


tri = 0
for i in range(1,1000):
    tri += i
    if check(tri,500):
        print(tri)
        break
        

jerryxjr1220

来个冷门的，用AArdio编写

import console;
import time.timer
 
console.setTitle("test");

var ys = function(n) {
        if (n==1){
                return 1;
        }
        var c = 2;
        for(i=2;n**0.5;1){
                if(n%i==0){
                        if(i*i==n){
                                c += 1;
                        }
                        else{
                                c += 2;
                        }
                        
                }
        
        }
        return c
}

time.timer.start();
sum = 0;
s = 1;
while(ys(sum) <= 500){
        sum += s
        s++

}

console.print(ys(sum), sum);

console.print(time.timer.endTick())
 
console.pause();

576     76576500
1690.6272414923
请按任意键继续 ...

运行速度差不多比python高4~5倍

阿bang

import time


start = time.time()
n = 0
num = 0
while True:
    factcount = 2
    n += 1
    num += n
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            if num != i ** 2:
                factcount += 2
            else:
                factcount += 1
    if factcount > 500:
        break
print n, num
print time.time() - start

塔利班

def pri(x):
    t={}
    while x!=1:
        z=x
        if x%2==0:
            x=x//2
            if 2 in t:
                t[2]+=1
            else:
                t[2]=1
            continue
        elif x%3==0:
            x=x//3
            if 3 in t:
                t[3]+=1
            else:
                t[3]=1
            continue
        else:
            for i in range(3,int(x**0.5)+1,2):
                if x%i==0:
                    if i in t:
                        t[i]+=1
                    else:
                        t[i]=1
                    x=x//i
                    break
        if z==x:
            x=1
            if z in t:
                t[z]+=1
            else:
                t[z]=1
    res=1
    for each in t:
        res*=(t[each]+1)
    return res
x=200
while pri(x*(x+1)//2)<=500:
    x+=1
print(x*(x+1)//2)