前言:
当前朋友们对“python输出指定范围的素数”都比较着重,小伙伴们都想要分析一些“python输出指定范围的素数”的相关知识。那么小编同时在网络上汇集了一些有关“python输出指定范围的素数””的相关资讯,希望看官们能喜欢,兄弟们一起来学习一下吧!程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。
例如:输出100-200范围内符合条件的素数
#!/usr/bin/python#coding:utf-8#author:菜就多练呀from math import sqrtc = 0leap = 1for m in range(101, 201): k = int(sqrt(m + 1)) for i in range(2, k + 1): if m % i == 0: leap = 0 break if leap == 1: print('%4d' % m) c += 1 leap = 1print('范围内的素数共有%d个' % c)
判断素数的常用方法:
1.试除法
def is_prime(n): if n <= 1: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return Trueprint(is_prime(100))
2.米勒-拉宾素性测试
#!/usr/bin/python#coding:utf-8#author:菜就多练呀import randomdef miller_rabin(n, k=5): if n <= 1: return False if n == 2 or n == 3: return True if n % 2 == 0: return False r, s = 0, n - 1 while s % 2 == 0: r += 1 s //= 2 for _ in range(k): a = random.randrange(2, n - 1) x = pow(a, s, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return Truedef is_prime(n): if n <= 1: return False if n == 2 or n == 3: return True if n % 2 == 0: return False return miller_rabin(n)print(is_prime(5))
3.素数筛法
#!/usr/bin/python#coding:utf-8#author:菜就多练呀def sieve_of_eratosthenes(n): primes = [True] * (n + 1) primes[0], primes[1] = False, False for i in range(2, int(n**0.5) + 1): if primes[i]: for j in range(i*i, n + 1, i): primes[j] = False return [x for x in range(n + 1) if primes[x]]def is_prime(n): if n <= 1: return False if n in sieve_of_eratosthenes(n): return True return Falseprint(is_prime(100))
4.费马小定理
#!/usr/bin/python#coding:utf-8#author:菜就多练呀import randomdef fermat_little_theorem(n): if n <= 1: return False if n == 2 or n == 3: return True if n % 2 == 0: return False a = random.randint(2, n - 1) if pow(a, n - 1, n) != 1: # 修改:检查 pow 结果是否为 1 return False return Truedef is_prime(n): if n <= 1: return False if n == 2 or n == 3: return True if n % 2 == 0: return False return fermat_little_theorem(n)# 测试print(is_prime(7)) # 输出:True
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #python输出指定范围的素数