Project Euler个人答案:2~8
博客专区 > fzyz_sb 的博客 > 博客详情
Project Euler个人答案:2~8
fzyz_sb 发表于3年前
Project Euler个人答案:2~8
  • 发表于 3年前
  • 阅读 28
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 学生专属云服务套餐 10元起购>>>   

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





共有 人打赏支持
粉丝 352
博文 209
码字总数 447144
×
fzyz_sb
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: