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

欧拉计划 · 发表于 2015-4-21 16:16:20

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由欧拉计划于 2015-4-21 16:17 编辑

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 个约数的三角形数是多少？

翅膀团 · 发表于 2015-8-2 20:48:28

本帖最后由翅膀团于 2015-11-16 14:13 编辑

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

复制代码

如果有错误希望指出

匿名鱼油 *发表于 2015-12-2 15:41:29* · 发表于 2015-12-2 15:41:29

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

ppsuc_wuj · 发表于 2016-3-2 22:21:33

游客 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 · 发表于 2016-6-13 18:18:36

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

愤怒的大头菇 · 发表于 2016-8-24 12:40:02

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 · 发表于 2016-8-26 23:30:13

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 · 发表于 2016-9-17 17:17:49

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 · 发表于 2016-10-11 16:36:43

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 · 发表于 2016-11-23 15:51:14

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

芒果加黄桃 · 发表于 2017-1-9 17:01:59

# 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

渡风 · 发表于 2017-1-14 01:50:51

本帖最后由渡风于 2017-1-22 19:35 编辑

此代码使用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 · 发表于 2017-2-6 23:05:06

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 · 发表于 2017-3-14 18:59:03

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 · 发表于 2017-4-2 09:31:52

本帖最后由 JonTargaryen 于 2017-4-2 10:13 编辑

约数个数分解定理
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;
}

复制代码

天之南 · 发表于 2017-5-1 01:43:38

#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 · 发表于 2017-9-12 16:51:26

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 · 发表于 2017-9-29 15:29:01

来个冷门的，用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 · 发表于 2018-4-3 19:34:12

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

复制代码

塔利班 · 发表于 2018-8-27 17:14:19

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)

复制代码

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

评分