python判断素数：查找所有素数_编程找出n的所有素数python

素数（质数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

判断素数

第一种：

就是暴力解法普通查找：遍历2-n的值找出是否存在因数

def IsPrime1(num):
    if num == 2 or num == 3:
        return 1
    else:
        for i in range(2, num):
            if num % i == 0:
                return 0
        else:
                return 1
1
2
3
4
5
6
7
8
9

第二种：

在第一种的基础上缩短遍历的值的数量

如果一个自然数是非素数，那么它的所有因数（除1和本身）中，必存在某个因数小于等于其开方值

那么我们的任务就是遍历2-sqrt(n)，如果存在因数，那么是非素数，如果不存在因数，即该数位素数。

import math

def IsPrime2(num):
    if num == 2 or num == 3:
        return 1
    else:
        n = int(math.sqrt(num))
        for i in range(2, n + 1):# range（start，stop[,step]）中的stop值不在遍历范围内
            if num % i == 0:
                return 0
        else:
                return 1
1
2
3
4
5
6
7
8
9
10
11
12

第三种：

在第二种的基础上继续减少遍历值

首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；

简单证明一下：大于5的自然数：…6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6x+6，6x+7…

不在6x（即6的倍数）相邻两侧的数为6x+2，6x+3，6x+4，可以被2,3整除，显然不是素数，可以将这一大部分值排除掉。

注意：在6x相邻两侧的值不一定是素数。例如35…

接下来的任务就是判断6x相邻两侧的数：此时判断质数可以6个为单元快进，即将方法（2）循环中step设为6，加快判断速度。

原因是：假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被 6i，6i+2，6i+4整除，则n至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；

另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。

综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可。

import math

def IsPrime3(num):
    if num == 2 or num == 3:
        return 1
    if num % 6 != 1 and num % 6 != 5:
        return 0
    n = int(math.sqrt(num))
    for i in range(5, n + 1, 6):
        if num % i == 0 or num % (i + 2) == 0:
            return 0
    else:
        return 1
1
2
3
4
5
6
7
8
9
10
11
12
13

以上三种是比较经典的三种判断素数方法

查找素数：

第一种：

查找一定范围内的所有素数，直接遍历，找出符合条件的数并打印（或者存进一个数组里面）

def PrintAllPrime(n):
    for s in range(2,n+1):
        if IsPrime1(s) == 1:
            print(s)

1
2
3
4
5

第二种：

我们一起学习一种高级的思想：生成器构造筛选

原理上比较简单：构造一个大概的序列，从序列中遍历筛选不符合的，剩下的即为素数

实现上：构造一个可以包括所有素数的序列，然后定义一个筛选函数对其进行元素移除；定义一个生成器，不断的生成下一个素数，这样就可以根据自己的需要生成一定范围内的素数

def odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n  # 返回一个Iterator

def not_divisible(n):
    return lambda x: x % n > 0

def primes():
    yield 2
    it = odd_iter()  # 初始序列
    while True:
        n = next(it)  # 返回序列的第一个数
        yield n
        it = filter(not_divisible(n), it)  # 构造新序列

# 打印10以内的素数：
m=10
for n in primes():
    if n <= m:
        print(n)
    else:
        break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

好了，今天的分享就到这里！如果你是0基础，想要学习Python的话，可以试试我整理的这份Python全套学习资料，0基础入门+进阶实战，学完就可以自己在网上帮人写写脚本，接单赚米了~

需要的可以自行扫描下方SCDN官方认证二维码免费领取

资料包括：Python永久使用安装包、Python web开发，Python爬虫，Python数据分析，人工智能、机器学习、大厂面试题、Python练习题、Python实战案例源码等学习教程。带你从零基础到精通！

零基础Python学习资源介绍

一、Python所有方向的学习路线

Python所有方向路线就是把Python常用的技术点做整理，形成各个领域的知识点汇总，它的用处就在于，你可以按照上面的知识点去找对应的学习资源，保证自己学得较为全面。

二、Python学习软件

工欲善其事，必先利其器。学习Python常用的开发软件都在这里了！

三、Python入门学习视频

还有很多适合0基础入门的学习视频，有了这些视频，轻轻松松上手Python~

四、Python练习题

每节视频课后，都有对应的练习题哦，可以检验学习成果哈哈！

五、Python实战案例

光学理论是没用的，要学会跟着一起敲代码，动手实操，才能将自己的所学运用到实际当中去，这时候可以搞点实战案例来学习。这份资料也包含在内的哈~

六、Python面试资料

我们学会了Python之后，有了技能就可以出去找工作啦！下面这些面试题是都来自阿里、腾讯、字节等一线互联网大厂，并且有阿里大佬给出了权威的解答，刷完这一套面试资料相信大家都能找到满意的工作。

七、资料领取

上述完整版Python全套学习资料已经上传CSDN官方，需要的小伙伴可自行微信扫描下方CSDN官方认证二维码免费领取