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?

复制代码
from math import sqrt 
import time 
def natSum(n):
    x = 1
    count = 0
    sum = 0
    while count <= n:
        sum += x
        count = 0
        for i in range(1,int(sqrt(sum))+1):
            if sum % i == 0:
                count += 2
        if sqrt(sum)==int(sqrt(sum)): 
                count -= 1
        print x,sum,count,n

        x += 1
    
natSum(500)
'''
start=time.time() 
now=2
num=1
t = 0
while t <= 500 : 
    num=num+now 
    now+=1
    t=0
    for x in range(1,int(sqrt(num))+1): 
        if num%x==0: 
            t+=2
    if sqrt(num)==int(sqrt(num)): 
        t=t-1

    print num
print num 
print time.time()-start 
'''
        
复制代码

目录
相关文章
|
算法
【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number
【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number
123 0
【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number
Highly divisible triangular number( Problem 12)
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,
1015 0
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
103 1
|
6月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
7月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
48 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
39 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
96 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
102 0
LeetCode 313. Super Ugly Number
|
算法
LeetCode 306. Additive Number
累加数是一个字符串,组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
125 0
LeetCode 306. Additive Number
|
算法
LeetCode 268. Missing Number
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
92 0
LeetCode 268. Missing Number