题目12：第一个拥有超过500个约数的三角形数是多少？
本帖最后由 欧拉计划 于 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 that28is 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-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);
}
如果有错误希望指出 严重超时了，电脑跑不出来 游客 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 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多秒出结果 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)) length:576 76576500
# 第一个拥有超过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
snlist = []
suml = 0
for i in range(50000):
suml += i
snlist.append (suml)
for each in snlist:
output = yueshu(each)
lensum = output
if lensum >500:
yuesum = list(output)
fin = each
break
else:
pass
print (yuesum, 'length:%d' % lensum, fin) 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)) 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 =
if len(temp)>count/2: break
numlist =
numlist.extend(temp)
return trinum,len(numlist),sorted(numlist)
f = euler12(500)
print('{}\n\nresult:{} count:{} time:{}'.format(f,f,f,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
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 = *n
primes,primes=False,False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes = False
return
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-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=;
Rank=Temp;
end
end
Output=length(Rank)+1;
end
end 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 = * (number * 8)
list_primes = False
list_primes = False
list_result = []
while len(list_result) < number:
for i in range(2, len(list_primes)):
if list_primes:
for j in range(i ** 2, len(list_primes), i):
list_primes = False
list_result.clear()
for k in range(2, len(list_primes)):
if list_primes:
list_result.append(k)
list_primes.extend( * 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
start = time.clock()
print(triangular_2())
end = time.clock()
print('程序执行了%fs。' %(end - start))
执行结果：
程序执行了1.046565s。 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 10:13 编辑
约数个数分解定理
http://baike.baidu.com/item/%E7%BA%A6%E6%95%B0%E4%B8%AA%E6%95%B0%E5%AE%9A%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;
} 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
来个冷门的，用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倍
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+=1
else:
t=1
continue
elif x%3==0:
x=x//3
if 3 in t:
t+=1
else:
t=1
continue
else:
for i in range(3,int(x**0.5)+1,2):
if x%i==0:
if i in t:
t+=1
else:
t=1
x=x//i
break
if z==x:
x=1
if z in t:
t+=1
else:
t=1
res=1
for each in t:
res*=(t+1)
return res
x=200
while pri(x*(x+1)//2)<=500:
x+=1
print(x*(x+1)//2)
页:
[1]
2