文档章节

Project Euler个人答案:2~8

fzyz_sb
 fzyz_sb
发布于 2015/02/27 22:19
字数 840
阅读 40
收藏 0

1:

2:

>>> def fib(n):
	result = []
	a, b = 1, 2
	while a < n:
		result.append(a)
		a, b = b, a + b
	return result

>>> sum(filter(lambda x: x % 2 == 0, fib(4000000)))
4613732
3:

def Prime(n):
    primeArr = [2, 3]
    result = -1
    if n == 2 or n == 3:
        return n
    if n < 2:
        return result
    #递归1~n的每一个元素,判断是否为素数
    x = 4
    while x < n:
        if primeArr[-1] > (x // 2):
            divArr = filter(lambda y: y <= (x // 2), primeArr)
        else:
            divArr = primeArr + range(1, x)[primeArr[-1]:(x // 2)]
        #print divArr
        for y in divArr:
            if x % y == 0:
                break
        else:
            primeArr.append(x)
            result = x
        x += 1
    return result

def PrimeFactor(n):
    #存储因素分解
    result = []
    #存储素数
    primeArr = [2]

    while n != 1:
        x = primeArr[-1]
        if n % x == 0:
            result.append(x)
            print result
            n = n // x
        else:
            #说明最大的素数已经被分解,寻求更大的素数
            while True:
                x += 1
                for y in primeArr:
                    if x % y == 0:
                        break
                else:
                    primeArr.append(x)
                    break
    return result[-1]
4:

def isPalindrome(num):
    """判断数字是否为回文数字"""
    s = str(num)
    rs = s[::-1]
    return s == rs

def PrimeFactor(n):
    #存储因素分解
    result = []
    #存储素数
    primeArr = [2]

    while n != 1:
        x = primeArr[-1]
        if n % x == 0:
            result.append(x)
            n = n // x
        else:
            #说明最大的素数已经被分解,寻求更大的素数
            while True:
                x += 1
                for y in primeArr:
                    if x % y == 0:
                        break
                else:
                    primeArr.append(x)
                    break
    return result

def proByTwoNum(result, num):
    twoFactor = []
    if result[-1] > num:
        return []
    x = num - 1
    while True:
        y = x
        for f in result:
            if y % f == 0:
                y = y // f
        if y != 1:
            x = x - 1
        else:
            twoFactor = [x, reduce(lambda x, y: x * y, result) // x]
            break
    for f in twoFactor:
        if f >= num:
            return []
    return twoFactor
    
def largestPalindrome(num):
    """找到最大的回文数字"""
    proNum = num * num
    while proNum:
        proNum -= 1
        #如果为回文数字,则进行因素分解
        if isPalindrome(proNum):
            result = PrimeFactor(proNum)
            #如果因素分解的结果可以成为两个小于num的数的乘积,则proNum为最大的回文数字
            twoFactor = proByTwoNum(result, num)
            if len(twoFactor) == 2:
                return proNum
5:

def PrimeFactor(n):
    #存储因素分解
    result = []
    #存储素数
    primeArr = [2]

    while n != 1:
        x = primeArr[-1]
        if n % x == 0:
            result.append(x)
            n = n // x
        else:
            #说明最大的素数已经被分解,寻求更大的素数
            while True:
                x += 1
                for y in primeArr:
                    if x % y == 0:
                        break
                else:
                    primeArr.append(x)
                    break
    return result

def listToDict(result):
    """将列表转换为字典:键为数值,值为出现的次数:[1, 2, 3, 2, 3]-->{1:1,2:2,3:2}"""
    d = {}
    for n in result:
        if n in d:
            d[n] += 1
        else:
            d[n] = 1
    return d

def multiple(num):
    """生成可被1~num所有数整除的最小整数"""
    result = 1
    #字典d用于存储最大的因数分解
    TotalDict = {}
    for x in range(2, num + 1):
        d = listToDict(PrimeFactor(x))
        for key in d:
            if key in TotalDict:
                if d[key] > TotalDict[key]:
                    TotalDict[key] = d[key]
            else:
                TotalDict[key] = d[key]
    print TotalDict
    for key in TotalDict:
        result *= pow(key, TotalDict[key])
    return result
6:

def SumSquareDifference(n):
    return pow(sum(range(1, n + 1)), 2) - sum([x * x for x in range(1, n + 1)])
7:

def Prime(n):
    primeArr = [2, 3]
    result = -1
    if n == 2 or n == 3:
        return n
    if n < 2:
        return result
    #递归1~n的每一个元素,判断是否为素数
    x = 4
    while x < n:
        if primeArr[-1] > (x // 2):
            divArr = filter(lambda y: y <= (x // 2), primeArr)
        else:
            divArr = primeArr + range(1, x)[primeArr[-1]:(x // 2)]
        #print divArr
        for y in divArr:
            if x % y == 0:
                break
        else:
            primeArr.append(x)
            result = x
        x += 1
    return result

def isPrime(n):
    """判断其是否为素数"""
    primeArr = [2, 3]
    if n == 2 or n == 3:
        return True
    x = 2
    while x <= n // 2:
        if n % x == 0:
            return False
        x += 1
    return True 

def PrimeIndex(index):
    primeNum = 1
    while index > 0:
        primeNum += 1
        if isPrime(primeNum):
            index -= 1
    return primeNum
8:

s = """7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"""
def proByNums(count):
    result = 1
    index = 0
    length = len(s)
    while index < length - count + 1:
        sub = s[index:index + count]
        sumForSub = reduce(lambda x, y: x * y, map(int, sub))
        if sumForSub > result:
            result = sumForSub
        index += 1
    return result





© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 408
博文 209
码字总数 447144
作品 0
武汉
程序员
纸笔的力量(2011-01-01)

对 Mathematica 着迷了,虽然我知道这热情不会持续多久。还是喜欢在解决问题中学习,这次是 Project Euler 的第 38 问。 提问:一个数依次×1,×2,……把所得连接成一个 9 位数,如果这个 ...

Pope怯懦懦地
2017/12/09
0
0
18 个锻炼编程技能的网站

本文由伯乐在线 -Reset 翻译。未经许可,禁止转载! 英文出处:codecondo。欢迎加入翻译组。 编程几乎已经成为了人类所知每个行业的必要组成部分,它帮助组织和维护大型系统的方式是无可比拟...

伯乐在线
2016/08/03
0
0
Bad Coder(2011-01-04)

再优美的语言,如果你真的把它当作草稿来用,也还真是可以写出一些自惭形秽的-_-! 依然以奋斗在 Project Euler 界的我为例(这次的热情貌似久了一点)。 Problem 27 我们拿到的只是坐标,并非...

Pope怯懦懦地
2017/12/09
0
0
51nod 1024 矩阵中不重复的元素

1024 矩阵中不重复的元素 Project Euler 难度:2级算法题 收藏 关注 一个m*n的矩阵。 该矩阵的第一列是a^b,(a+1)^b,.....(a + n - 1)^b 第二列是a^(b+1),(a+1)^(b+1),.....(a + n - 1)^(b+1...

Fire_to_cheat_
02/23
0
0
欧拉函数(Euler Function)

Cover 欧拉函数 在数论,对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目(φ(1)=1)。此函数以其首名研究者欧拉命名(Euler'so totient function),它又称为Euler's totient function、...

SpiffyEight77
2017/07/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

angular 解决其他电脑不能访问的问题。

ng serve --host 0.0.0.0 --disable-host-check

miaojiangmin
今天
1
0
优酷视频文件怎么转换格式

  以前在优酷上下载视频都只是在手机上观看,但随着科技的发展,对于视频的要求也逐渐增多,不再只是观看视频那么简单,在精彩的部分还会将其单独分割出来,然后进行视频剪辑,可以做出我们...

萤火的萤火
今天
0
0
数据结构:散列

在一个数据结构中查找key元素,用顺序查找、二分查找都需要经过一系列关键之比较才能查找到结果,平均查找长度与数据量有关,元素越多比较次数就越多。 如果根据元素的关键字就能知道元素的存...

京一
今天
1
0
Apache RocketMQ 正式开源分布式事务消息

近日,Apache RocketMQ 社区正式发布4.3版本。此次发布不仅包括提升性能,减少内存使用等原有特性增强,还修复了部分社区提出的若干问题,更重要的是该版本开源了社区最为关心的分布式事务消...

阿里云云栖社区
今天
32
0
使用JavaScript和MQTT开发物联网应用

如果说Java和C#哪个是最好的开发语言,无疑会挑起程序员之间的相互怒怼,那如果说JavaScript是动态性最好的语言,相信大家都不会有太大的争议。随着越来越多的硬件平台和开发板开始支持JavaS...

少年不搬砖老大徒伤悲
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部