python求素数

# !/usr/bin/python

from math import sqrt

from time import time

def Find_Prime_Nu(num):

    Prime_Nu=[2]

    for i in range(3,num+1,2):

        Evolution_Num = int(i**(0.5))

        for j in Prime_Nu:

            if j > Evolution_Num:

                Prime_Nu.append(i)

                break

            if i % j == 0:

                break

    return Prime_Nu

def prime(max):

    p = [2,3]

    for i in range(5, max + 1, 2):

        is_prime = True

        l = int(sqrt(i))

        for j in p:

            if j > l:

                break

            if i % j == 0:

                is_prime = False

                break

        if is_prime:

            p.append(i)

    return p

def bench(max):

    t0=time()

    Find_Prime_Nu(max)                

    t1=time()

    prime(max)

    t2=time()

    print max,t1-t0,t2-t1

bench(1000)

print "================"

bench(100000)

print "================="

bench(1000000)

减少赋值对比次数很明显能提高效率