python使用筛选法计算小于给定数字的所有素数

本文实例为大家分享了python计算小于给定数字的所有素数的具体代码，供大家参考，具体内容如下

代码思路：首先列出指定范围内所有候选数字，然后从前往后依次选择一个数字去除以后面所有数字，能够被整除的肯定不是素数，把这些数字过滤掉，然后重复这个过程，直到选择的除数大于最大数字的平方根为止。代码主要演示内置函数filter()和切片的用法，实际上这个算法的效率并不是很高。

def primes2(maxNumber):
  '''筛选法获取小于maxNumber的所有素数'''
  #待判断整数
  lst = list(range(3, maxNumber, 2))
  #最大整数的平方根
  m = int(maxNumber**0.5)
  for index in range(m):
    current = lst[index]
    #如果当前数字已大于最大整数的平方根，结束判断
    if current > m:
      break
    #对该位置之后的元素进行过滤
    lst[index+1:] = list(
      filter(
        lambda x: 0 if not x%current else x,
        lst[index+1:]))
  #2也是素数
  return [2] + lst

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

您可能感兴趣的文章:

  • python素数筛选法浅析
  • Python cookbook(数据结构与算法)筛选及提取序列中元素的方法
  • Python3.4实现从HTTP代理网站批量获取代理并筛选的方法示例
  • python如何在列表、字典中筛选数据
赞 (0)

相关推荐

  • python如何在列表、字典中筛选数据

    python如何在列表.字典中筛选数据? 实际问题有哪些? 1.过滤掉列表[3,9,-1,10.-2......] 中负数 2.筛选出字典 {'li_ming':90,'xiao_hong':60,'li_kang':95,'bei_men':98} 中值高于90的项 3.筛选出集合{3,9,-1,10.-2......]中能被3整除的数 问题1如何解决? 最普通方法: #!/usr/bin/python3 def filter_l(data): res = [] for i in data:

  • python素数筛选法浅析

    python素数筛选法浅析

    原理: 素数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数.在加密应用中起重要的位置,比如广为人知的RSA算法中,就是基于大整数的因式分解难题,寻找两个超大的素数然后相乘作为密钥的.一个比较常见的求素数的办法是埃拉托斯特尼筛法(the Sieve of Eratosthenes) ,说简单一点就是画表格,然后删表格,如图所示: 从2开始依次往后面数,如果当前数字一个素数,那么就将所有其倍数的数从表中删除或者标记,然后最终得到所有的素数. 有一个优化: 标记2和3的倍数

  • Python3.4实现从HTTP代理网站批量获取代理并筛选的方法示例

    本文实例讲述了Python3.4实现从HTTP代理网站批量获取代理并筛选的方法.分享给大家供大家参考,具体如下: 最近在写爬虫,苦于不采用代理的情况下,默认的IP不出几分钟就被封了,故而只能寻找代理.原以为找到HTTP代理就万事大吉了,没想到从那个网站获取的代理大部分都是不能用的,只有少部分能用...故而无奈之下,只能从那些代理网站大量获取代理IP,然后再拿过来进行进一步的筛选,将有效的代理IP提取出来,留待进一步使用. 筛选的主要原理是,通过main函数提取到未经筛选的代理rawProxyLi

  • Python cookbook(数据结构与算法)筛选及提取序列中元素的方法

    本文实例讲述了Python筛选及提取序列中元素的方法.分享给大家供大家参考,具体如下: 问题:提取出序列中的值或者根据某些标准对序列做删减 解决方案:列表推导式.生成器表达式.使用内建的filter()函数 1.列表推导式方法:存在一个潜在的缺点,如果输入数据非常大可能会产生一个庞大的结果,考虑到该问题,建议选择生成器表达式 # Examples of different ways to filter data mylist = [1, 4, -5, 10, -7, 2, 3, -1] prin

  • python使用筛选法计算小于给定数字的所有素数

    本文实例为大家分享了python计算小于给定数字的所有素数的具体代码,供大家参考,具体内容如下 代码思路:首先列出指定范围内所有候选数字,然后从前往后依次选择一个数字去除以后面所有数字,能够被整除的肯定不是素数,把这些数字过滤掉,然后重复这个过程,直到选择的除数大于最大数字的平方根为止.代码主要演示内置函数filter()和切片的用法,实际上这个算法的效率并不是很高. def primes2(maxNumber): '''筛选法获取小于maxNumber的所有素数''' #待判断整数 lst =

  • python微元法计算函数曲线长度的方法

    计算曲线长度,根据线积分公式: ,令积分函数 f(x,y,z) 为1,即计算曲线的长度,将其微元化: 其中 根据此时便可在python编程实现,给出4个例子,代码中已有详细注释,不再赘述 ''' 计算曲线长度,根据线积分公式: \int_A^Bf(x,y,z)dl,令积分函数为1,即计算曲线的长度 ''' import numpy as np from mpl_toolkits.mplot3d import * import matplotlib.pyplot as plt ## 求二维圆周长,

  • 利用PHP计算有多少小于当前数字的数字方法示例

    给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目. 换而言之,对于每个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j != i 且 nums[j] < nums[i] . 以数组形式返回答案. 示例 1: 输入:nums = [8,1,2,2,3] 输出:[4,0,1,1,3] 解释: 对于 nums[0]=8 存在四个比它小的数字:(1,2,2 和 3). 对于 nums[1]=1 不存在比它小的数字. 对于 nums[2]=

  • c++素数筛选法

    c++素数筛选法

    素数(又称质数):指在大于一的自然数中,只能被1和它自身整除的自然数: 素数筛选法是指一种非常规的素数判定方法,比较高效率: 原理:任何数的整数倍必定不是素数,大于二的偶数必定不是素数. 我们以找出100以内的素数为例,利用原理,我们可以首先排除偶数是素数,然后进一步判断奇数 实现将偶数标记为0,素数标记为1:(也可以用一个bool数组将偶数标记为false,奇数标记为true) 下面是全部代码 #include <iostream> #include <cmath> #defin

  • C语言:利用指针编写程序,用梯形法计算给定的定积分实例

    题目要求 利用指针编写程序,用梯形法计算下列公式中的定积分: 参考代码 首先说明一下指针的用处:因为所传递的参数均为数字,并不需要使用指针提高效率,故这里使用指针指向函数. 请注意calc()函数中的这一语句: double(*pfunction)() = &function; 即实现了我所描述的过程. 代码如下: #include <stdio.h> #include <math.h> double function(double x){ return (double)(

  • Python基于回溯法子集树模板解决数字组合问题实例

    Python基于回溯法子集树模板解决数字组合问题实例

    本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题 找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.

  • Python基于回溯法子集树模板解决0-1背包问题实例

    Python基于回溯法子集树模板解决0-1背包问题实例

    本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

  • Python基于回溯法子集树模板解决最佳作业调度问题示例

    Python基于回溯法子集树模板解决最佳作业调度问题示例

    本文实例讲述了Python基于回溯法子集树模板解决最佳作业调度问题.分享给大家供大家参考,具体如下: 问题 给定 n 个作业,每一个作业都有两项子任务需要分别在两台机器上完成.每一个作业必须先由机器1 处理,然后由机器2处理. 试设计一个算法找出完成这n个任务的最佳调度,使其机器2完成各作业时间之和达到最小. 分析: 看一个具体的例子: tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 最优调度顺序:1 3 2 处理时间:18 这3个作业的6种可能的调度方案是1,2,3:1

  • Python基于回溯法子集树模板解决找零问题示例

    Python基于回溯法子集树模板解决找零问题示例

    本文实例讲述了Python基于回溯法子集树模板解决找零问题.分享给大家供大家参考,具体如下: 问题 有面额10元.5元.2元.1元的硬币,数量分别为3个.5个.7个.12个.现在需要给顾客找零16元,要求硬币的个数最少,应该如何找零?或者指出该问题无解. 分析 元素--状态空间分析大法:四种面额的硬币看作4个元素,对应的数目看作各自的状态空间,遍历状态空间,其它的事情交给剪枝函数. 解的长度固定:4 解的编码:(x1,x2,x3,x4) 其中x1∈[0,1,2,3], x2∈[0,1,2,3,4

随机推荐