Python-求素数程序-白红宇

Python-求素数程序

阅读量：6155 次

发布时间：2019-06-21

本文共 5868 字，大约阅读时间需要 19 分钟。

#!/usr/bin/python#-*- coding: utf-8 -*-import timefrom 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:

---------------------------------