五月 18

Project Euler 第10题(更改)

原来写的时候可能表述不是很清楚,某些同学造成了一些误解,所以我更改一下,抱歉。

最近对python有强烈的兴趣,于是就开始学习了,目前只是学了一些基本的语法。我看的书是Beginning.Python.From.Novice.to.Professional,2nd.Edition,感觉这本书挺好的,唯一的不足就是没有一道习题。学编程哪能光看书不编几个程序啊,于是我就开始找习题。突然想到原来看比特之理这个博客时好像有个叫什么Eular的网站,里面有很多的小题目,于是我就上去做了。我现在只做了前10题,目前为止都觉得很简单,基本不需要思考,使用暴力解法可以轻松解决。呵呵,这篇日志为什么叫这个题目呢,难道这个题目有点难?我们来看下:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
就是说算出两百万以下的所有素数的和。

这也太简单了吧。。。好吧,我做这题花了点时间。。。我刚开始没太注意(英语太渣),潜意识里觉得是“算出前两百万个素数之和”,呵呵。我就把题目当成是计算前两百万个素数之和(不是两百万以下的素数)算了。然后开始用python编程,一开始肯定想到的是最简单的方法,先写一个判断某数是否是否素数的函数,然后一个一个判断,将所有素数加起来。

import math
import time
start=time.clock()
def ifprime(n):    #判断一个数是否是素数的函数
    if n==2:return 1
    for i in range(2,math.ceil(math.sqrt(n))+1):
        if n%i==0:
            return 0
    return 1
nn=2000000  #两百万
number=1
count=0
ssum=0
while 1:
   number+=1
   if ifprime(number):
       count+=1
       ssum+=number
       
   if count==nn:
        break
print(ssum)
end=time.clock()
print("time:",end-start)

运行一下,半天没有结果啊,我以为是哪里错了进了死循环就检查了一遍,发现没有问题。再运行,3分钟了还没出结果。然后我通过程序运行中打印一些结果的方法知道了这是因为数据实在是太大了,要计算很久。这时我就想哎呀这题看来有点难度了不能像前面几题通过纯暴力手段得到结果。于是就开始优化程序。很容易想到,判断n是否为素数的那个函数占用了大量的时间,而且这个算法很低级,从2一直模到 \sqrt(n) 。其实完全没有模合数的必要。我就这样想,如果有个素数表,取模的时候从这表里取,自然效率就高多了。可是这个表从哪里来呢?可以一边判断素数,一边生成这个表。

import time
start=time.clock()
import math
nn=2000000   #两百万个素数
number=1    #当前计算的数
count=0     #得到的素数个数
ssum=0    #素数之和
primetable=[2]   #得到的总的素数表
primetable2=[2]  #截取的需要遍历的素数表
def ifprime(n):
    if n==2:return 1
    while 1:
        if primetable2[-1]**2<n:
            primetable2.append(primetable[len(primetable2)])
        else:break
    for i in primetable2:  #i在截取的素数表中遍历
        if n%i==0:
            return 0
    primetable.append(n)  #n是素数,加进素数表中
    return 1

while 1:
    number+=1
    if ifprime(number):
        count+=1
        ssum+=number
        flag=0
    if count==nn:   #如果得到两百万个素数就退出循环
        break
print(ssum)
end=time.clock()
print("time:",end-start)

用这个改进的方法后效率肯定大为提高,但是。。。。对于这么大量的数据还是要很长的时间,经过测试,python3.4用时165秒,python2.7用时96秒(这两个版本貌似速度差别很大啊,新的版本居然更慢,网上查的资料看确实有这一说,但是具体机制我现在还不太清楚)。那个改进之前的就没有运行了。不过,效率有没有提高还是要用数据说话,对于前十万个素数之和,改进前的算法是11秒,改进后的是3秒(python3.4)。还是有很明显的区别的。

都说python运行效率低,正好借此机会来感受一下。对于那个没有改进的算法,计算前十万个素数之和,python用时11秒,而C语言用时1秒!!差距怎么会这个大!!好吧,呵呵。
C语言代码:

#include<stdio.h>
#include<time.h>  
#include<math.h>
char ifprime(unsigned long n)
{
  int i;
  if(n==2)return 1;
  for(i=2;i<sqrt(n)+1;i++)
  {
    if(n%i==0)return 0;
  }
  return 1;
  
}
void main()
{
  clock_t start, finish;  
  double  duration;  
  unsigned long ssum=0,i,number=1,count=0;
  long nn=100000;
  start = clock();  
  while(1)
  {
    number++;
    if(ifprime(number))
    {
      count++;
      ssum+=number;
    }
    if(count==nn)
      break;
  }
  printf("%ld\n",ssum);
  finish = clock(); 
  duration = (double)(finish - start) / CLOCKS_PER_SEC;  
  printf( "%f seconds\n", duration );   
}

最后总结一下啊,用python2.7计算前两百万个素数的时间是96秒。感觉这个时间好长啊,一定还有很多可以优化的地方。有时间我再想一想。
好吧继续做题。

标签:, ,

Posted 2014年5月18日 by zhangzimou in category computer&internet
  1. 刚刚试验了一下,我计算前100万个素数之和,判别法就用2到n^0.5一个个试除(就是你一开始的没有优化的方法),用matlab计算,用时应该在两秒内。matlab效率估计跟python差不多~