PythonTip >> 博文 >> python

Python-求素数程序

zihua 2014-01-16 18:01:17 点击: 797 | 收藏


#!/usr/bin/python
#-*- coding: utf-8 -*-
import time
from math import sqrt
#根据概念判断:
def SelectPrime1(Num):
    #2是素数
    Prime = [2]
    #循环计算3-n之间的数
    for i in range(3,Num):
        #print ">>>i = %d" %i
        for j in range(2, i, 1):
            #print ">j = %d" %j
            if i % j == 0:
                #print ">>j = %d" %j
                break
        else:
            Prime.append(i)
    else:
        #print Prime
        print ">>>The number of prime between 0 and %d is %d" %(Num,len(Prime))

#去掉偶数的判断,时间复杂度O(n/2)
def SelectPrime2(Num):
    #2是素数
    Prime = [2]
    #循环计算3-n之间的数
    for i in range(3,Num):
        #print ">>>i = %d" %i
        if i % 2 == 0:
            continue
        for j in range(3, i, 2):
            #print ">j = %d" %j
            if j != "" and (i % j == 0):
                #print ">>j = %d" %j
                break
        else:
            Prime.append(i)
    else:
        #print Prime
        print ">>>The number of prime between 0 and %d is %d" %(Num,len(Prime))
def SelectPrime3(Num):
    #2是素数
    Prime = [2]
    #循环计算3-n之间的数
    for i in range(3,Num):
        #print ">>>i = %d" %i
        #int(math.sqrt(i))输出的是比i的开平方小的最大整数,range(m,n)这里,range()函数产生一个从m至n-1的整数列表,因此需要‘+1’
        for j in range(2, int(sqrt(i))+1, 1):
            #print ">j = %d" %j
            if j != "" and (i % j == 0):
                #print ">>j = %d" %j
                break
        else:
            Prime.append(i)
    else:
        #print Prime
        print ">>>The number of prime between 0 and %d is %d" %(Num,len(Prime))
        
def SelectPrime4(Num):
    #2是素数
    Prime = [2]
    #循环计算3-n之间的数
    for i in range(3,Num):
        #print ">>>i = %d" %i
        #int(math.sqrt(i))输出的是比i的开平方小的最大整数,range(m,n)这里,range()函数产生一个从m至n-1的整数列表,因此需要‘+1’
        k = int(sqrt(i))+1
        for j in range(2, k, 1):
            #print ">j = %d" %j
            if j != "" and (i % j == 0):
                #print ">>j = %d" %j
                break
        else:
            Prime.append(i)
    else:
        #print Prime
        print ">>>The number of prime between 0 and %d is %d" %(Num,len(Prime))
        
#1. 在循环条件中重复调用sqrt(i)显然是比较浪费时间的;
#2. 判断素数,只要2~sqrt(i)间的质数不能整除i即可;
def SelectPrime5(Num):
    #2是素数
    Prime = [2]
    #循环计算3-n之间的数
    for i in range(3,Num):
        stop = 0
        #print ">i = %d" %i
        #int(math.sqrt(i))输出的是比i的开平方小的最大整数,range(m,n)这里,range()函数产生一个从m至n-1的整数列表,因此需要‘+1’
        k = int(sqrt(i))+1
        #print ">k is %d" %k
        #print ">Prime is %s, the length of Prime is %d" %(Prime, len(Prime))
        #print ">stop is %d" %stop
        #print ">Prime[stop] is %d" %Prime[stop]
        #while Prime[stop] < k and stop < len(Prime)会报错IndexError: list index out of range
        while stop < len(Prime)and Prime[stop] < k:
            #print ">>>stop is %d" %stop
            stop += 1
        #print ">stop is %d" %stop
        for j in range(0, stop, 1):
            #print ">Prime[%d] = %d" %(j,Prime[j])
            if i % Prime[j] == 0:
                break
        else:
            Prime.append(i)
    else:
        #print Prime
        print ">>>The number of prime between 0 and %d is %d" %(Num,len(Prime))
        
if __name__ == "__main__":
    Num = input("Please enter the Number: ")
    #Calculate for Algorithem1
    starttime = time.time()
    print "Algorithem1 Start Time is: %s" %starttime
    SelectPrime1(Num)
    endtime = time.time()
    print "Algorithem1 End Time is: %s" %endtime
    print "Algorithem1 Executed Time is %s:" %(endtime - starttime)
    print "---------------------------------"
    #Calculate for Algorithem2
    starttime = time.time()
    print "Algorithem2 Start Time is: %s" %starttime
    SelectPrime2(Num)
    endtime = time.time()
    print "Algorithem2 End Time is: %s" %endtime
    print "Algorithem2 Executed Time is %s:" %(endtime - starttime)
    print "---------------------------------"
    #Calculate for Algorithem3
    starttime = time.time()
    print "Algorithem3 Start Time is: %s" %starttime
    SelectPrime3(Num)
    endtime = time.time()
    print "Algorithem3 End Time is: %s" %endtime
    print "Algorithem3 Executed Time is %s:" %(endtime - starttime)
    print "---------------------------------"
    #Calculate for Algorithem4
    starttime = time.time()
    print "Algorithem4 Start Time is: %s" %starttime
    SelectPrime4(Num)
    endtime = time.time()
    print "Algorithem4 End Time is: %s" %endtime
    print "Algorithem4 Executed Time is %s:" %(endtime - starttime)
    print "---------------------------------"
    #Calculate for Algorithem5
    starttime = time.time()
    print "Algorithem5 Start Time is: %s" %starttime
    SelectPrime5(Num)
    endtime = time.time()
    print "Algorithem5 End Time is: %s" %endtime
    print "Algorithem5 Executed Time is %s:" %(endtime - starttime)
    print "---------------------------------"
>>>
Please enter the Number: 100000
Algorithem1 Start Time is: 1374654766.32
>>>The number of prime between 0 and 100000 is 9592
Algorithem1 End Time is: 1374654940.05
Algorithem1 Executed Time is 173.726000071:
---------------------------------
Algorithem2 Start Time is: 1374654940.06
>>>The number of prime between 0 and 100000 is 9592
Algorithem2 End Time is: 1374655034.08
Algorithem2 Executed Time is 94.0160000324:
---------------------------------
Algorithem3 Start Time is: 1374655034.09
>>>The number of prime between 0 and 100000 is 9592
Algorithem3 End Time is: 1374655035.58
Algorithem3 Executed Time is 1.49199986458:
---------------------------------
Algorithem4 Start Time is: 1374655035.59
>>>The number of prime between 0 and 100000 is 9592
Algorithem4 End Time is: 1374655037.03
Algorithem4 Executed Time is 1.43600010872:
---------------------------------
Algorithem5 Start Time is: 1374655037.03
>>>The number of prime between 0 and 100000 is 9592
Algorithem5 End Time is: 1374655039.21
Algorithem5 Executed Time is 2.18399977684:
---------------------------------
原文链接:http://my.oschina.net/u/1178546/blog/146773

作者:zihua | 分类: python | 标签: python | 阅读: 797 | 发布于: 2014-01-16 18时 |