龙空技术网

python经典案例:输出指定范围内符合条件的素数

菜就多练呀 117

前言:

当前朋友们对“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输出指定范围的素数