菜鸡一枚欢迎指正
目录
特点
合数都是被他的最小素数因子筛去的
思路
定义两个list : status : 表示整数状态，一开始除0，1外都默认为素数，合数标记为False prime：存放素数
遍历2->n 如果status为True，表示当前为i为素数，加入到prime数组。然后遍历prime列表pj把i*pj标记为合数。
注意：当i为合数，p[j]为i的最小素因子，那么标记完status[i*p[j]] 后就结束对于prime的遍历。例如：当i为4时，此时prime=[2,3], 标记status[i * 2]为False，因为2为4的最小素因子，所以此时结束对prime的遍历
当i大于n的一半后，i*prime[j]都大于n,所以无需再标记合数只需添加后续的素数即可
优化
由于偶数肯定不是素数所以可以只考虑奇数的情况
代码
#判断一个数是否为素数
def is_prime(n):#返回的是最小素因子，如果为素数返回0
if n == 0 or n==1:
return 1
if n == 2:
return 0
if n%2==0:#偶数不是素数
return 2
m = int(n ** 0.5)
status = [True for _ in range(int(m / 2) + 1)] # 3,5,7,9,11,13,15,17,19,21,23
prime = []
for i in range(3, m + 1, 2):
if status[int((i - 3) / 2)]:
if n % i ==0:
return i
prime.append(i)
for pj in prime: # 遍历prime
if pj * i > m: # 越界结束遍历
break
status[int((pj * i - 3) / 2)] = False
if i % pj == 0:#p[j]为i的最小素因子,此时结束遍历
break
return 0
def prime_list(n):
if n == 0 or n==1:
return []
if n == 2:
return [2]
m = int(n ** 0.5)
status = [True for _ in range(int(n/2) + 1)] # 3,5,7,9,11,13,15,17,19,21,23
prime = []
for i in range(3, n+1, 2): # 遍历3-m,跳过所有偶数
if status[int((i - 3) / 2)]:
prime.append(i)
for pj in prime: # 遍历prime
if pj * i > n: # 当i大于n的一半后，i*prime[j]都大于n,所以无需再标记合数只需添加后续的素数即可
break
status[int((pj * i - 3) / 2)] = False
if i % pj == 0: # p[j]为i的最小素因子,此时结束遍历
break
return [2]+prime
n=int(input("请输入一个整数:"))
pr=is_prime(n)
if pr:
print("{0}不是素数，最小素因子为{1}".format(n,pr))
else:
print("{0}是素数".format(n))
pl=prime_list(n)
print("1到{0}的素数有{1}".format(n,pl))
