首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Python|欧拉筛法质数

问题描述 我们知道第一个质数是 2、第二个质数是 3、第三个质数是 5……请你计算第 2020 个质数是多少?...解决方案 当看到这种寻找质数的问题,很多人第一时间想到的便是二重循环暴力查找,如果只找前几个质数,可以使用这种暴力查找的方法。但如果要找第2020个质数,第9999个质数,这种暴力方法就不适用了。...这个时候就可以使用筛法来质数,本文介绍的是欧拉筛法。其运用的原理是质数的倍数一定不是质数。因此将质数的倍数直接标记成合数,以达到筛选质数的目的。...代码: def ouLaShai(n): lis = [True for i in range(n + 1)] # 用于筛选记录合数 lis2 = [] # 存质数...而到后面的某个质数prime2去筛i * prime2的时候,就有i * prime2 == x * prime * prime2,因而prime和prime2都是i * prime2的质因子。

1.6K20
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    Numpy 100以内质数

    一百以内质数之和 判断是否为质数 判断一个整数是否为质数比较简单,即除了自身和1以外不可被别的数整除。不过根据数学理论证明,不用从2检查到n,到int(sqrt(n))+1即可,可以提高效率。...+1): if num % i == 0: return False return True 利用循环 简单粗暴的方式,从1循环到100,一次判断是否为质数...,若是质数,则加到ans上,若不是直接跳过。...向量化的理解,就本例子而言,循环的思想是每次取一个数,对其判断是否为质数;向量化是取这个数组为变量,直接对其所有元素判断是否为质数,然后返回一个同size的数组。...返回一个布尔型数组,比如np_arr = array([1,2,3,4]);那is_prime_vec(np_arr)返回array([False, True, True, False]),因为2,3是质数

    1.3K50

    C++经典算法题-筛选质数

    15.Algorithm Gossip: Eratosthenes 筛选质数 说明 除了自身之外,无法被其它整数整除的数称之为质数,要求质数很简单,但如何快速的 求出质数则一直是程式设计人员与数学家努力的课题...,在这边介绍一个着名的 Eratosthenes质数方法。...解法 首先知道这个问题可以使用回圈来求解,将一个指定的数除以所有小于它的数,若可以 整除就不是质数,然而如何减少回圈的检查次数?如何求出小于N的所有质数?...19 20 21 N 先将2的倍数筛去: 2 3 5 7 9 11 13 15 17 19 21 N 再将3的倍数筛去: 2 3 5 7 11 13 17 19 N 再来将5的倍数筛去,再来将7的质数筛去...,再来将11的倍数筛去 ,如此进行到最后留下的 数就都是质数,这就是Eratosthenes筛选方法(Eratosthenes Sieve Method)。

    41420

    python用递归筛选法N以内的孪生质数(孪生素数)

    本人最近读完一本书《质数的孤独》,里面讲到孪生质数,就想查一下孪生质数的分布情况。...新建List,然后从第0位开始,如果后面的能被这个数整除,则从数组中移除改元素,以此类推,最后留下的就是质数(素数)。...python版本与java版本不同,java可以在遍历list的时候删除该元素,可以对循环变量i进行i--的操作,防止以后的get(i)方法报错,python不支持这个操作只能是拿到被删除的元素,然后在遍历结束以后再去删除.../usr/bin/python3 class Test(): def __init__(self): print ("fan") def get(self,list,st...:"+str(a)+"----"+str(b)) 这里备注一下:python为了防止内存溢出,限制了递归的深度,所以直接10000以内的还不行,会报错: RecursionError: maximum

    2.6K20

    Python 计算质数提升

    今天在做 Python 学习的时候,发现自己对于代码的递归和循环的控制,还有实现编程的思考太过简单了,一道简单的编程题,浪费掉了我很多的时间才完成,真的是太不应该了,这倒题是说给定一个数,可以是整数,也可以是浮点数...,然后计算这个数之后的5个质数,并输出出来。...现在整理一下思路,求解质数不说了,可以直接使用上次的方案: def prime(n): if n == 1: return False for i in range(2,...if n % i == 0: return False return True 然后就是进入到计算连续的五个数中,首先考虑的是,我需要输出过程中使用五次循环,但是我本身找质数的过程中也应该使用一个计数器循环...primes.append(str(start)) i += 1 start += 1 print(','.join(primes)) 这次给自己提了个醒,虽然 Python

    91520

    Python数学计算工具2、判断质数、遍历质数

    质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数(规定1既不是质数也不是合数)。...# 计算质数 import os os.system("title 质数查询与判断:") def isZhi(num): # 质数大于 1 if num > 1:...86933994 下面是打包过程: 使用打包工具:【pip install pyinstaller】 安装完成后注意使用语法: pyinstaller -F -p D:\save\Exe\studys\Python...\exe\Lib -i D:\save\myclass\Python\core\pythonProject\python.ico demo5.py -n " 质数判断与质数范围查询工具" 可以看到我使用了...2个绝对路径,绝对路径1是Python环境的包所在的位置,如果包不全的话需要自己通过pip进行下载,建议修改完镜像位置再下载。

    81930

    groovy使用stream语法递归筛选法N以内的质数

    本人最近读完一本书《质数的孤独》,里面讲到孪生质数,就想查一下孪生质数的分布情况。...其中主要用到了计算质数(素数)的方法,搜了一下,排名前几的都是用for循环来做的,感觉略微麻烦了一些,在比较一些还是觉得用递归筛选法来解决这个问题。...新建List,然后从第0位开始,如果后面的能被这个数整除,则从数组中移除改元素,以此类推,最后留下的就是质数(素数)。...0) list.remove(i--); } if (list.size() > ++tt) get(list, tt); } 然后再去做相邻元素差求得孪生质数...(孪生素数),贴一下10000以内孪生质数(孪生素数)全部的代码: List list = new ArrayList(); for (int i = 2; i

    1.7K30

    【模板小程序】小于等于N范围内的质数

    1 //筛法N以内的素数(普通法+优化),N>=2 2 #include 3 #include 4 #include 5 using...;//这里保存了小于等于N的素数 26 } 附:素数筛法原理(具体出处记不得了,可以留言我补上) 【算法-ACM-素数】素数的算法及其复杂度分析 关于搜寻一定范围内素数的算法及其复杂度分析...当然没 接触过程序竞赛之前我也只会这一种n以内素数的方法。-_-~)不会耗时很多.     但是当n很大的时候,比如n=10000000时,n*sqrt(n)>30000000000,数量级相当大。...如果i已经被判断不是质数了,那么再找到i后面的质数来把这个质 数的倍数筛掉。      一个简单的筛素数的过程:n=30。    ...这上面的所有的素数筛选的算法都可以再进一步化为二次筛选法,就是欲求n以内的素数,就先把sqrt(n)内的素数 出来,用已经求得的素数来筛出后面的合数。

    1.3K10

    java用递归筛选法N以内的孪生质数(孪生素数)

    本人最近读完一本书《质数的孤独》,里面讲到孪生质数,就想查一下孪生质数的分布情况。...其中主要用到了计算质数(素数)的方法,搜了一下,排名前几的都是用for循环来做的,感觉略微麻烦了一些,在比较一些还是觉得用递归筛选法来解决这个问题。...新建List,然后从第0位开始,如果后面的能被这个数整除,则从数组中移除改元素,以此类推,最后留下的就是质数(素数)。...0) list.remove(i--); } if (list.size() > ++tt) get(list, tt); } 然后再去做相邻元素差求得孪生质数...(孪生素数),贴一下10000以内孪生质数(孪生素数)全部的代码: List list = new ArrayList(); for (int i = 2; i

    1.8K10
    领券