精华内容
下载资源
问答
  • 返回序列中的数 yield n it = filter(_not_divisible(n), it) # 埃氏筛选法,产生筛选后新的序列 list_yc = list() for n in primes(): if n == 17: list_yc.append(n) break list_yc.append(n) print(list_yc) 输出...

    代码如下

    def _odd_iter(): # 构建奇数序列 从3开始

    n = 1

    while True:

    n = n + 2

    yield n

    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) # 埃氏筛选法,产生筛选后新的序列

    list_yc = list()

    for n in primes():

    if n == 17:

    list_yc.append(n)

    break

    list_yc.append(n)

    print(list_yc)

    输出如下

    [2, 3, 5, 7, 11, 13, 17]

    代码分析

    我不明白代码对别人来说是怎样的难度,我仅说说我自己第一次看到这个代码产生的疑问

    it = filter(_not_divisible(n), it) 这一行代码中,调用方法 _not_divisible 方法 时,内部的lambda: x: x % n > 0中 x 的值是多少

    it 是一个 Iterator, 每次next时才会返回一个值(for语句里面是每一次循环都调用一次next), 那序列中的 9 是怎样被 3 筛选掉的呢?

    第一个问题:

    这个地方是一个闭包调用,_not_divisible 返回了一个函数,而那个函数作用于 Iterator 中的每一个元素, 即 x 的值是 Iterator 中的每一个值

    第二个问题:

    首先追踪 _not_divisible 方法执行的每一步

    改写 _not_divisible 如下

    def _not_divisible(n):

    def lam(x):

    if n == 3:

    print('_not_divisible, n == 3', x)

    elif n == 5:

    print('_not_divisible, n == 5', x)

    return x % n > 0

    return lam

    输出如下

    _not_divisible, n == 3 5

    _not_divisible, n == 3 7

    _not_divisible, n == 5 7

    _not_divisible, n == 3 9

    _not_divisible, n == 3 11

    _not_divisible, n == 5 11

    _not_divisible, n == 3 13

    _not_divisible, n == 5 13

    _not_divisible, n == 3 15

    _not_divisible, n == 3 17

    _not_divisible, n == 5 17

    埃氏筛选法 可以明显的看到用3,5筛选序列时是交替进行的。

    可以肯定的是,用3筛选的时候没有一次性筛选所有的数字(事实上也不可能,因为_odd_iter是无限序列)

    在用数字5筛选的之前,又使用了3筛选。那就是意味着用 3 筛选的方法被挂起了,每当有新数字,该方法会被唤醒且调用。以此类推,每一个数字对应的筛选函数都保存起来了(因为它要作用于序列中的每一个数字)

    嗯。。。以上想法仅仅是个人折腾代码,调试出来的猜测,尚未向python大神确认。

    思绪来的快去的也快,偶尔在这里停留

    展开全文
  • 质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合数相对立的两个概念,...

    3a2c5c47719654b2eb3ed26ac95e70d8.png

    质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数是与合数相对立的两个概念,二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题,如哥德巴赫猜想等。算术基本定理证明每个大于1的正整数都可以写成素数的乘积,并且这种乘积的形式是唯一的。这个定理的重要一点是,将1排斥在素数集合以外。如果1被认为是素数,那么这些严格的阐述就不得不加上一些限制条件。 前几天偶尔的有朋友问python怎么判断素数的方法,走网上查了查,总结了python脚本判断一个数是否为素数的几种方法:

    1.运用python的数学函数

    import math

    def isPrime(n):

    if n <= 1:

    return False

    for i in range(2, int(math.sqrt(n)) + 1):

    if n % i == 0:

    return False

    return True

    2.单行程序扫描素数

    from math import sqrt

    N = 100

    [ p for p in range(2, N) if 0 not in [ p% d for d in range(2, int(sqrt(p))+1)] ]

    运用python的itertools模块

    from itertools import count

    def isPrime(n): www.ddpool.cn

    if n <= 1:

    return False

    for i in count(2):

    if i * i > n:

    return True

    if n % i == 0:

    return False

    3.不使用模块的两种方法方法1:

    def isPrime(n):

    if n <= 1:

    return False

    i = 2

    while i*i <= n:

    if n % i == 0:

    return False

    i += 1

    return True

    方法2:

    def isPrime(n):

    if n <= 1:

    return False

    if n == 2:

    return True

    if n % 2 == 0:

    return False

    i = 3

    while i * i <= n:

    if n % i == 0:

    return False

    i += 2

    return True

    eg:求出20001到40001之间的质数(素数)既然只能被1或者自己整出,那说明只有2次余数为0的时候,代码如下:

    #!/usr/bin/python

    L1=[]

    for x in xrange(20001,40001):

    n = 0

    for y in xrange(1,x+1):

    if x % y == 0:

    n = n + 1

    if n == 2 :

    print x

    L1.append(x)

    print L1

    结果如下:

    20011

    20021

    20023

    20029

    20047

    20051

    20063

    20071

    20089

    20101

    20107

    20113

    20117

    20123

    20129

    20143

    20147

    20149

    20161

    20173

    ….

    展开全文
  • 计算素数的一个方法是埃氏筛,它的算法理解起来非常简单:首先,列出从2开始的所有自然数,构造一个序列:2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...取序列的第一个数2,它一定是...

    计算素数的一个方法是埃氏筛法,它的算法理解起来非常简单:

    首先,列出从2开始的所有自然数,构造一个序列:

    2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    取序列的第一个数2,它一定是素数,然后用2把序列的2的倍数筛掉:

    3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    取新序列的第一个数3,它一定是素数,然后用3把序列的3的倍数筛掉:

    5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    取新序列的第一个数5,然后用5把序列的5的倍数筛掉:

    7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    不断筛下去,就可以得到所有的素数。

    # 构造一个从3开始的奇数序列

    def _odd_iter():

    n = 1

    while True:

    n += 2

    yield n

    def _not_visible(n):

    return lambda x: x % n > 0

    def primes():

    yield 2

    it = _odd_iter()

    while True:

    n = next(it)

    yield n

    it = filter(_not_visible(n), it)

    for n in primes():

    if n < 1000:

    print(n)

    else:

    break

    logo.gif

    展开全文
  • 原理:素数,指在一个大于1的自然数...一个比较常见的求素数的办法是埃拉托斯特尼筛(the Sieve of Eratosthenes),说简单一点就是画表格,然后删表格,如图所示:从2开始依次往后面数,如果当前数字一个素数,那么...

    原理:

    素数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。在加密应用中起重要的位置,比如广为人知的RSA算法中,就是基于大整数的因式分解难题,寻找两个超大的素数然后相乘作为密钥的。一个比较常见的求素数的办法是埃拉托斯特尼筛法(the Sieve of Eratosthenes),说简单一点就是画表格,然后删表格,如图所示:

    2018319144504544.gif?2018219144523

    从2开始依次往后面数,如果当前数字一个素数,那么就将所有其倍数的数从表中删除或者标记,然后最终得到所有的素数。

    有一个优化:

    标记2和3的倍数的时候,6被标记了两次。所以从i的平方开始标记,减少很多时间。

    比如3的倍数从9开始标记,而不是6,并且每次加6。

    除了2以外,所有素数都是奇数。奇数的平方还是奇数,如果再加上奇数就变成了偶数一定不会是素数,所以加偶数(2倍素数)。

    预先处理了所有偶数。

    注意:1既不是素数也不是合数,这里没有处理1。

    #! prime.py

    import time

    def primes(n):

    P = []

    f = []

    for i in range(n+1):

    if i > 2 and i%2 == 0:

    f.append(1)

    else:

    f.append(0)

    i = 3

    while i*i <= n:

    if f[i] == 0:

    j = i*i

    while j <= n:

    f[j] = 1

    j += i+i

    i += 2

    P.append(2)

    for i in range(3,n,2):

    if f[i] == 0:

    P.append(i)

    return P

    def isPrime(n):

    if n > 2 and n%2 == 0:

    return 0

    i = 3

    while i*i <= n:

    if n%i == 0:

    return 0

    i += 2

    return 1

    def primeCnt(n):

    cnt = 0

    for i in range(2,n):

    if isPrime(i):

    cnt += 1

    return cnt

    if __name__ == '__main__':

    start = time.clock()

    n = 10000000

    P = primes(n);

    print("There are %d primes less than %d"%(len(P),n))

    #for i in range(10):

    # print(P[i])

    print("Time: %f"%(time.clock()-start))

    #for n in range(2,100000):

    # if isPrime(n):

    # print("%d is prime"%n)

    #print("%d is "%n + ("prime" if isPrime(n) else "not prime"))

    start = time.clock()

    n = 1000000

    print("There are %d primes less than %d"%(primeCnt(n),n))

    print("Time: %f"%(time.clock()-start)

    用素数筛选法求1千万以内的素数用了5.767s,

    普通素数判断法求1百万以内的素数用了9.642s,

    用C++素数筛选法求1亿以内的素数用了0.948s,

    用C++普通素数判断法求1千万以内的素数用了3.965s,

    可见解释语言确实比编译语言慢很多。

    附C++程序,用了位压缩优化空间

    #include

    #include

    #include

    using namespace std;

    #define N 100000001

    unsigned f[(N>>5)+5];

    int p[5761456],m;

    void init()

    {

    int i,j;

    for(i=4;i

    f[i>>5]|=1<<(i&0x1F);

    p[m++]=2;

    for(i=3;i*i

    if(!(f[i>>5]&(1<<(i&0x1F))))

    {

    p[m++]=i;

    for(j=i*i;j

    f[j>>5]|=1<<(j&0x1F);

    }

    for(;i

    if(!(f[i>>5]&(1<<(i&0x1F))))

    p[m++]=i;

    }

    int is_prime(int n)

    {

    int i;

    for(i=0;p[i]*p[i]<=n;i++)

    if(n%p[i]==0)

    return 0;

    return 1;

    }

    int isPrime(int n)

    {

    if(n>2 && n%2==0)

    return 0;

    int i=3;

    while(i*i<=n)

    {

    if(n%i==0)

    return 0;

    i+=2;

    }

    return 1;

    }

    int main()

    {

    int n=0,i;

    clock_t st=clock();

    init();

    /*for(i=2;i<10000000;i++)

    if(isPrime(i))

    n++;*/

    printf("%d %dms ",m,clock()-st);

    /*while(~scanf("%d",&n),n)

    {

    i=lower_bound(p,p+m,n+1)-p;

    printf("%d ",i);

    }*/

    return 0;

    }

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

    展开全文
  • python程序设计:筛选法求素数

    千次阅读 2020-03-14 23:58:48
    筛选法求素数 1. 题目要求: 使用列表实现筛选法求素数:编写程序,输入一个大于2的自然数,然后输出小于该数字的所有素数组成的列表。 2. 思路解析: 整个题目要求还是比较简单的,只要知道怎么筛选除素数就可以了...
  • 代码如下: (具体内置函数可以自行搜索,我主要记录这样求素数的原理即好处,帮助大家和自己体验一下这种高级的感觉【来自小白的乐趣】)1 maxNumber = int(input("请输入一个大于2的自然数"))2 lst = list(range(2...
  • python 用列表筛选法求素数

    千次阅读 2020-11-29 22:53:55
    import math def prime(n): alist=[x for x in range(2,n+1)] k=0 for i in range(0,math.floor(math.sqrt(n+1))): m=0 for j in range(2,n+1): ...print(“所得的素数为:”,alist) n = int(input(“请输入一个大于2
  • Jupyter 使用列表实现筛选法求素数 使用列表实现筛选法求素数可以极大的提高计算机的运算速率。 maxNumber = int(input("请输入一个大于2的自然数:")) lst = list(range(2,maxNumber)) #最大整数的平方根 m = int...
  • Python法求素数

    2019-05-02 18:45:00
    l=[2]m,n=input().split()m=int(m)n=int(n)for i in range(m,n): flag=True for j in l: if i%j==0:#如果当前值可整除已筛选出的素数中的任意值,则改变flag,结束循环 flag=False break if flag:#添加该...
  • 输入一个大于2的自然数,输出小于该数字的所有素数组成的集合。 Code: maxNumber = int(input('请输入一个大于2的自然数:')) numbers = set(range(2,maxNumber)) #最大数的平方根,以及小于该数字的所有素数 m = ...
  • 题目: 给定两个四位素数a b,要求把a变换到b。变换的过程要保证:每次变换出来的数都是一个四位素数,而且当前这步的变换所得的素数与前一步得到的素数,只能有一个位置上的... 筛选法求素数,建表,搜索。 #...
  • 本段代码的主要作用是利用埃氏筛选法筛选出一个奇数数组中的素数。 def _odd_iter(): n = 1 while True: n = n+2 yield n def _not_divisible(y): return lambda x : x % y &amp;amp;gt; 0 def primes():...
  • python语言对于计算机专业的学生,不管是计算机软件还是物联网,都是很重要的一种编程语言,python未来在人工智能方向上是会有很大的贡献程度...python学习—–使用列表实现筛选法求素数目录一、列表实现筛选法求素数
  • 原理:素数,指在一个大于1的自然数...一个比较常见的求素数的办法是埃拉托斯特尼筛(the Sieve of Eratosthenes),说简单一点就是画表格,然后删表格,如图所示:从2开始依次往后面数,如果当前数字一个素数,那么...
  • 来自百度百科–埃拉托色尼筛选法: (1)先把1删除(现今数学界1既不是质数也不是合数) (2)读取队列中当前最小的数2,然后把2的倍数删去 (3)读取队列中当前最小的数3,然后把3的倍数删去 (4)读取...
  • 原理:素数,指在一个大于1的自然数...一个比较常见的求素数的办法是埃拉托斯特尼筛(the Sieve of Eratosthenes) ,说简单一点就是画表格,然后删表格,如图所示:从2开始依次往后面数,如果当前数字一个素数,那...
  • 其中主要用到了计算质数(素数)的方法,搜了一下,排名前几的都是用for循环来做的,感觉略微麻烦了一些,在比较一些还是觉得用递归筛选法来解决这个问题。新建List,然后从第0位开始,如果后面的能被这个数整除,则从...
  • ')) hits=0 for i in range(times): #循环 x=random() #产生随机数 y=random() if x*x+y*y(4.0*hits/times) 运行结果如下: 2、使用列表实现筛选法求素数 编写程序,输入一个大于 2 的自然数,然后输出小于该数字的...
  • python实现筛法求素数

    千次阅读 2018-10-25 16:05:37
    def iters():#先构造一个从3开始的奇数序列。这是一个生成器,并且是一个无限序列 ...def isinit(n):#筛选函数 return lambda x:x%n&gt;0 def prime(): yield 2 it=iters()# 初始序列 whi...

空空如也

空空如也

1 2 3 4
收藏数 75
精华内容 30
关键字:

python筛选法求素数

python 订阅