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

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：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 个约数的三角形数是多少？


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

小火木

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

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

老忘

__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

严重支持

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

思路：
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

lingtingliushen

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

# -*- 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

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

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

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

挥舞乾坤

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))

宝贝归来

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

小剑剑

楼主等我别开车

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