ProjectEuler,1-10题

先介绍一下，ProjectEuler，欧拉工程，是一个国外的练习数论的网站，总共300多道题目。

网址是http://projecteuler.net/problems，有个特点是可以使用任何编程语言，或者自己手算，得到答案提交就可以了。

这个和OJ是不一样的。提交通过以后，可以去论坛看看那别人的解决方法，以及参与讨论。

好久没有动手做题了，那天看到论坛又有人在说，就来做做。我使用的语言是python，Life is short，you need Python

前面的题目很基础，但是刷水体不是我的风格，所以我尽量用高效的，不一样的的方法来解决。

1Add all the natural numbers below one thousand that are multiples of 3 or 5.

没什么特别的，用容斥就可以了

2By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
这一题是寻找一个小于4000000的最大的那个fibonacci数，
答案很小，朴素方法几行就写完了，但是我还是选择用高级方法
我们可以用矩阵快速幂乘来以O(logN)的时间获得第N个fibonacci数，然后我们选定范围二分答案就可以了
3Find the largest prime factor of a composite number.
寻找一个数的最大的质因子，直接分解质因数就可以了。数量比较小，用的最基础的分解质因数的方法，有兴趣的同学可以看看
4Find the largest palindrome made from the product of two 3-digit numbers.
没想到什么好方法，暴力的
5What is the smallest number divisible by each of the numbers 1 to 20?
典型的最小公倍数，N个数的最小公倍数，等于LCM(A1,LCM(A2,A3,...An-1))
6What is the difference between the sum of the squares and the square of the sums?
好吧大整数的题目（python完全没有感觉...），暴力的
7Find the 10001st prime.
找第几个质数，因为数量稍大了，所以用了填充法筛质数，比较常用的方法
8Discover the largest product of five consecutive digits in the 1000-digit number.
这题可以注意到如果序列中有0，就全为0了。所以我们可以用0，分割序列，然后每个序列如果长度少于5 就可以直接skip
剩下的每个子序列单独暴力就ok了。
9Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.
算了半天，还是暴力的
10Calculate the sum of all the primes below two million.又是质数打表，直接copy代码ok
import mathdef PrimeList(N = None,limit = None):'''return first N primes or  primes <= limit'''if N ==None and limit ==None:raise Exception('need either N or limit')ans = [2,3]i = 5dt = 2while True:if N != None and len(ans) >= N : breakif limit != None and ans[-1] >= limit: break f = Truefor j in ans:if i%j == 0:f = Falsebreakif f:ans.append(i)i += dtdt = 6 - dtreturn ansdef PrimeListFill(limit):'''return primes <= limit'''A = [True] * (limit + 1)plist = PrimeList(limit=int(math.sqrt(limit)))for p in plist:n = 2 * pwhile n <= limit:A[n] = Falsen += pans = []for i in xrange(2,len(A)):if A[i]:ans.append(i)return ansdef main():L = PrimeListFill(2000000)print sum(L)if __name__ == '__main__':main()


1楼leihengxin4小时前
顶一下。