欧拉计划 1-10
2018-06-30 本文已影响260人
Ghibli_Someday
1、10以下的自然数中，属于3或5的倍数的有3，5，6，9，它们的和是23。找出1000以内，属于3或5的倍数的数字总和。
解题思路：过于简单，直接上代码
源码：
sum = 0
for n in range(1000):
if n%3==0 or n%5==0:
sum += n
print(sum)
>>>
233168
2、斐波那契数列中的每一项都被定义前两项之和。从1和2开始，其前十项是：1，2，3，5，8，13，21，34，55，89，…。思考斐波那契数列中不超过4百万的项，找出这些项中为偶数的项之和。
解题思路：
1、构造一个迭代器，返回菲波那切数列中的数字
2、使用filter筛选出小于400W的偶数，并使用sum函数进行求和
源码：
# 构建斐波那契迭代器
def fib(n):
a, b = 1, 1
while b < n:
yield b
a, b = b, a + b
# filter和lambda用法，不懂可自行百度
count = sum(list(filter((lambda x:x%2==0), fib(4000000))))
print(count)
'''
上述代码用简单的for来解释，即
sum = 0
for n in fib(4000000):
if n%2 == 0:
sum += n
print(sum)
'''
>>>
4613732
3、13195 的质数因子有5，7，13和29。求 600851475143 的最大质数因子是多少。
解题思路：
1、构造一个素数判断函数
2、构造一个函数求出一个数的所有公约数
3、筛选出为质数的公约数，并取出最大值
源码：
from math import sqrt
from time import time
# 素数判断函数，给一个值，如果返回True，则表示是素数，False表示为非素数
def is_prime(n):
if n > 1:
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(sqrt(n))+1, 2):
if n % i == 0:
return False
# for循环结束后，如无False，则返回True
return True
# 如 if n > 1 不成立，则返回False
return False
# 取得给定值的所有乘数因子
def factor(n):
L = []
for i in range(1, int(sqrt(n))+2):
if n%i == 0:
L.append(i)
L.append(n/i)
# set 去除相同的因子
return set(L)
start_time = time()
memb = list(filter(is_prime, factor(600851475143)))
memb.sort()
end_time = time()
print(memb)
print('Running time = ', end_time - start_time)
print('Largest prime factor is ', memb[-1])
>>>
[71, 839, 1471, 6857]
Running time = 0.113600015640
Largest prime factor is 6857
看到别人的一个方法，觉得也挺不错，速度更快，运用了递归
import math
import time
def judgePrimes(num):
if num%2 == 0:
return False
for i in range(3, int(math.sqrt(num))+1, 2):
if not num%i:
return False
else:
return True
#用了递归的方法
def bigPrimeNum(num):
if judgePrimes(num):
return num
for i in range(3,num):
if num%i == 0:
print(i)
return bigPrimeNum(num//i)
a = time.time()
if __name__ == '__main__':
print(bigPrimeNum(600851475143))
b = time.time()
print('Running time: ', b-a)
>>>
71
839
1471
6857
Running time: 0.0
4、一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是 9009 = 91 * 99。找出最大的由两个三位数乘积构成的回文数。
解题思路：
1、求出两个三位数乘积的范围中的回文数
2、该回文数可以由两个三位数乘积构成
源码：
from time import time
def palindrome():
a, b = 100 * 100, 999 * 999
while b > a:
if str(b)==str(b)[::-1]:
yield b
b -= 1
def factor(n):
for i in range(100, 1000):
if n%i==0 and len(str(int(n/i)))==3:
return i
start_time = time()
L = list(filter(factor, palindrome()))
x = factor(L[0])
y = int(L[0]/x)
end_time = time()
print('最大的由两个三位数乘积构成的回文数是:' + str(x*y) + '=' + str(x) + '*' + str(y))
print('耗时：', end_time - start_time)
>>>
最大的由两个三位数乘积构成的回文数是:906609=913*993
耗时： 0.47099995613098145
5、2520 是最小的能被 1-10 中每个数字整除的正整数。最小的能被 1-20 中每个数整除的正整数是多少？
解题思路：
源码：
def great_common_divisor(n1, n2):
return great_common_divisor(n2, n1%n2) if n2 > 0 else n1
def lowest_common_multiple(n1, n2):
return n1*n2 // great_common_divisor(n1, n2)
