Project Euler个人答案:2~8
Project Euler个人答案:2~8
fzyz_sb 发表于3年前
Project Euler个人答案:2~8
• 发表于 3年前
• 阅读 32
• 收藏 0
• 评论 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):
while index > 0:
index -= 1
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``````

×