小练习：20160503 第一个拥有超过500个约数的三角形数是多少？

冬雪雪冬 · 发表于 2016-5-3 08:39:15

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

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

x

本帖最后由冬雪雪冬于 2016-5-10 12:24 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题，并且你每做对一题，就可以下载到参考答案的pdf文件，看看你的实现方法与参考答案有什么不同，以利于迅速提高自己的水平。

登录/注册后可看大图

好了言归正传，我们开始做小练习。

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在5.10 10：00前完成，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

题目：

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

奖励：
对所有完成程序并得出正确答案的将给予加分奖励，优秀的将额外加分。
在完成一批题目后，将根据每期的完成情况总评评出最佳，会有神秘大奖。

小火木 · 发表于 2016-5-3 22:54:15

import math
def divisor(n):
result=[]
t=0
for i in range(1,int(math.sqrt(n))+1):
if n%i==0:
result.append(i)
if math.sqrt(n)==int(math.sqrt(n)):
t=1
return len(result)*2-t
def trinum(n):
result=0
for i in range(1,n+1):
result+=i
return result
i=1
stop=False
while 1:
for j in [i+2,i+3]:
num=trinum(j)
n=divisor(num)
if n>500:
print('第一个拥有超过500个约数的三角形数是：\n第%d个三角形数%d，共有%d个约数'%(j,num,n))
stop=True
if stop:break
i+=4

复制代码

EggyBruch · 发表于 2016-5-3 23:24:49

本帖最后由 EggyBruch 于 2016-5-5 19:06 编辑

import time
def tri_num(app_num):
startTime = time.time()
n = 1
sum = 0
count = 0
while count <= app_num:
sum = 0
count = 0
for i in range (1,n+1):
sum += i
triangle = sum
divisor = []
amount = 0
for x in range(1,triangle+1):
if triangle % x == 0:
divisor.append(x)
amount += 1
length = len(divisor)
if (divisor[length - 2]*divisor[length-1] == triangle or
divisor[length - 1]*divisor[length-1] == triangle):
break
count = 2*(amount - 1)
n += 1
print('第一个拥有超过%d个约数的三角形数为：'%(app_num),sum)
print('read: %.3fs '%(time.time()-startTime))

复制代码

第一个拥有超过500个约数的三角形数为： 76576500
read: 23.064s

老忘 · 发表于 2016-5-4 21:32:10

本帖最后由老忘于 2016-5-10 21:48 编辑

__author__ = '老忘'
#-*- coding: UTF-8 -*-
def getChildren(num):
#递归分解因式
import math
isZhishu = True
i = 2
square = int(math.sqrt(num)) + 1
while i <= square:
if num % i == 0:
list_submultiple.append(i)
isZhishu = False
getChildren(num / i)
i += 1
break
i += 1
if isZhishu:
list_submultiple.append(int(num))
n=1
while 1:
m=n*(n+1)/2
list_submultiple=[]
getChildren(m) #分解并存入 list_submultiple
list_submultiple_only=set(list_submultiple)#去重存入list_submultiple_only
#约数个数为每个质因数的指数加1并相乘
s=1
z=0
for val_lso in list_submultiple_only:
z=int(list_submultiple.count(val_lso))+1
s *=z
if s>500:
print(int(m))
break
else:
n +=1

复制代码

DingRan · 发表于 2016-5-4 21:56:11

严重支持

def factorNumber(num):
result = 0
i = 1
while True:
if num%i==0:
result += 1
if num/i!=i:
result += 1
i += 1
if i>num**0.5:
break
return result
def findTriNum(factorNum):
i = 1
triNum = 0
while True:
triNum += i
if factorNumber(triNum)>factorNum:
break
i += 1
return triNum
print(findTriNum(500))

复制代码

运行结果

>>>
76576500
>>>

复制代码

bacon6581 · 发表于 2016-5-5 10:37:09

本帖最后由 bacon6581 于 2016-5-5 23:12 编辑

思路：
1.依次列举三角形数
2.取该三角形数的算术平方根
3.判断该算术平方根是否整数
4.判断该三角形数依次能被多少自然数整除，自然数范围为：range（2，算数平方根取整）
-----------------------------------------
说明：
1.任何自然数都能被1和其本身整除。所以约束直接2起步
2.如果自然数能被小于算数平方根的数整除，则必然存在有一个大于算数平方根的数整除
即：能被小于算数平方根的自然数整除，则必有2个约数
如20能被2整除，则必然能被10整除；能被4整除，则必然能被5整除
3.如果该三角形数的算数平方根是整数，则只增加一个约数
如9的算数平方根是3。则只会增加一个约数3。（3*3=9）

from math import sqrt
n=1
num=1
while True:
n=n+1
num=num+n
m=2
if int(sqrt(num))==sqrt(num):
m-=1
for i in range(2，int(sqrt(num))+1):
if num%i==0:
m=m+2
if m>500:
break
print(n)
print(num)

复制代码

结果如图：
第12375个三角形数
数值：76576500

无标题.jpg

lingtingliushen · 发表于 2016-5-5 15:02:23

import time
begTime = time.clock()
def prime(trianglenum):
divisor=[]
while trianglenum != 1:
for i in range(2,trianglenum+1):
if trianglenum % i == 0:
trianglenum //= i
divisor.append(i)
break
return divisor
num=1
n=2
while num <=500:
num=1
s1=sum(range(1,n))
n+=1
divisor=prime(s1)
a1=list(set(divisor))
for each in a1:
count1=divisor.count(each)
num*=(count1+1)
print('因子',divisor)
s1=1
for each in divisor:
s1*=each
print('三角数%d 有%d个约数' %(s1,num))
print(time.clock() - begTime)

复制代码

因子 [2, 2, 3, 3, 5, 5, 5, 7, 11, 13, 17]
三角数76576500 有576个约数
5.7881082194113835

复制代码

vpo1 · 发表于 2016-5-6 17:08:23

# -*- coding: utf-8 -*-
"""
Created on Fri May 6 09:34:52 2016
@author:
"""
#定义一个计算约数个数的函数
def count_divisor(n):
t = int(n/2)
divisor_n=2
while t>1:
if n%t == 0:
t = t-1
divisor_n = divisor_n+1
#print(t,divisor_n)
else:
t = t-1
#print(t)
return(divisor_n)
#定义一个产生三角形数的函数
def delta(n):
sumn = 0
i=1
while i<n:
sumn = sumn+i
i = i+1
return(sumn)
#初始化，y是判断约数个数是否大于500的一个开关，C是三角形数的层数
y=1
c=1
#从第一层三角形数开始，当约数个数是500时，则结束，打印；不是的时候层数加1
while y>0:
number = delta(c)
divisor = count_divisor(number)
if divisor==500:
y=0
print("这个数是：%i"%number)
print("约数个数：%i"%divisor)
else:
c = c+1
print(c,number,divisor)

复制代码

这是笨办法

holdme · 发表于 2016-5-7 18:57:53

先实现功能，后续再改进;

import time
t_start = time.clock()
# 统计因数个数
def count_div(n):
if n==1:
return 1
if n==2:
return 2
div = []
while n>2:
for i in range(2,n+1):
if n%i == 0:
div.append(i)
n = int(n/i)
break
cou_div = 1
for i in set(div):
cou_div *= div.count(i)+1
return cou_div
# 确定搜索起始值
idx = 2*3*5*7*11*14*17*19 #最小的有256个因数的数
n = 100
while sum(i for i in range(n+1)) < idx:
n += 1
t = sum(i for i in range(n+1))
while count_div(t)<500:
n += 1
t = sum(i for i in range(n+1))
print('第一个拥有超过 500 个约数的三角形数是：%d'%t)
print('用时%s秒'%str(time.clock()-t_start))

复制代码

答案是：

第一个拥有超过 500 个约数的三角形数是：76576500
用时6.540758731005951秒

复制代码

zooo · 发表于 2016-5-7 21:48:39

本帖最后由 zooo 于 2016-5-10 15:26 编辑

import time
begTime = time.time()
def find_num(num) :
mid = num/2
if mid != num//2:
return 0
counter = 0
n=1
while True:
if num%n == 0 and n+1<mid:
counter += 2
mid = num//n
n += 1
if n>mid:
break
return(counter)
num =1
n =2
while True:
num +=n
n+=1
if find_num(num)>500:
break
print(num, time.time()-begTime)

复制代码

并行计算：2核电脑效率提高近一倍，电脑核心数量越多用时越短
并行模块下载地址：http://www.parallelpython.com/content/view/18/32/

代码：

import time, pp
begTime = time.time()
def find_num(start, end) :
for index in range(start, end+1):
num = 0.5*index*(index+1)
mid = num/2
if mid != num//2:
continue
counter = 0
n=1
while True:
if num%n == 0 and n+1<mid:
counter += 2
mid = num//n
n += 1
if n>mid:
break
if counter > 500:
return num
return 0
start = 1
end = 10000
step = int((end - start)/128 + 1)#将区间分成128段
job_server = pp.Server()
stopFlag = 0
while True:
res_list = []
for index in range(128):
starti = start + index * step
endi = min( start + index * (step+1), end )
res_list.append(job_server.submit(find_num, (starti, endi)))
for fun in res_list:
if fun():
stopFlag = 1
print(fun(), time.time()-begTime)
break
if stopFlag:
break
start += 10000
end += 10000

复制代码

挥舞乾坤 · 发表于 2016-5-8 00:21:17

本帖最后由挥舞乾坤于 2016-5-11 09:18 编辑

def fun(n):
r, i = 0, 0
while True:
i += 1
r += i
c = 0
if r % 2:
continue
for j in range(1,int(r **.5)+1):
if r % j == 0:
c += 2
if c >= n:
return r
print(fun(500))

复制代码

宝贝归来 · 发表于 2016-5-8 20:10:58

max_Y =5 # 公约数（计算130，用了40多秒，数越大，后面越慢）
s = 10000000 # 三角形数
h = 0
for i in range(1,s+1):
h = h + i
Y = []
for i3 in range(1,h+1):
if(h % i3 == 0):
Y.append(i3)
#print(i,h,':',Y)
if( len(Y) > max_Y ):
print('这是第 %d 个三角形数'%i,'第一个拥有 %d 个公约数'%max_Y)
print(h,':',Y)
break

复制代码

小剑剑 · 发表于 2016-5-10 12:08:13

楼主等我别开车

def fi(su):
i=1
inte=0
while i*i<=su:
if(su%i==0):
inte+=2
i+=1
if (i-1)**2==su:
inte-=1
return inte
mi=250**2
c=0
s=0
inte=0
while s<mi:
c+=1
s+=c
while inte<500:
c+=1
s+=c
inte=fi(s)

复制代码

12375

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

[技术交流] 小练习：20160503 第一个拥有超过500个约数的三角形数是多少？

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分