python判断是否是素数_python素数判断函数无import

'''
在python中实现:取出某个数值区间范围内的所有素数(prime)
素数定义为:对于一个正整数N,如果除了1和它本身,它再不能被任何正整数整除,则它是素数/质数
定义2是最小的素数
'''
import math
import time
def is_prime(num):
    return 0 not in [num%sub for sub in range(2,math.ceil(math.sqrt(num)))]
 # math.ceil(x)等价于 int(x)+1
 # 方法1
start1=time.time()
a=2
b=1000000
# p=[p for p in range(a,b) if 0 not in [p%temp for temp in range(2,int(math.sqrt(p))+1)]]
# 对于区间范围内中的任意一个整数,遍历在[2,sqrt(num)]区间中的所有数作为除数
# 得到余数构成列表，如果0不在列表中，说明当前的数值不能被任何一个因子整除，则当前的数是质数
# 将p添加到质数列表中
# print(p)
end1=time.time()
print(end1-start1)
# 59.1281213760376
# 方法2:利用python中的filter方法
'''
描述
filter() 函数用于过滤序列，过滤掉不符合条件的元素，返回一个迭代器对象，如果要转换为列表，可以使用 list() 来转换。
该接收两个参数，第一个为函数，第二个为序列，
序列的每个元素作为参数传递给函数进行判，然后返回 True 或 False，最后将返回 True 的元素放到新列表中。
语法
以下是 filter() 方法的语法:
filter(function, iterable)
'''
start2=time.time()
p2=list(filter(is_prime,range(a,b)))
print(p2)
end2=time.time()
# assert p2==p
print(end2-start2)
# 59.43475270271301

# 方法三:使用python自带的lambda方法
start3=time.time()
is_prime2=(lambda num:0 not in [num%sub for sub in range(2,math.ceil(math.sqrt(num)))])
p3=filter(is_prime2,range(a,b))
end3=time.time()
print(end3-start3)
# assert p2==p3

# 方法4：当判断到当前数值不是质数时，提前终止
start4=time.time()
p4=[]
for i in range(a,b):
    flag=True
    for factor in p4:#如果当前数值除以素数的余数不为0，则一定是素数，如果除以合数为0，则一定不是素数
        if factor>int(math.sqrt(i))+1:
            break
        elif i%factor!=0:
            flag=False
            break
    if flag:
        p4.append(i)
end4=time.time()
print(end4-start4)
print(p4)