V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
jiaosky
V2EX  ›  Python

埃氏筛法求素数的问题,请大神指教啊

  •  
  •   jiaosky · 2018-09-05 14:34:06 +08:00 · 1767 次点击
    这是一个创建于 2274 天前的主题,其中的信息可能已经有所发展或是发生改变。
    # 1.队列生成器
    def _odd_iter():
        n = 1
        while True:
            n = n + 2  # 偶数一定不是素数
            yield n
    
    
    # 2.筛选器
    def _not_divisible(nn):
        return lambda x: print('x:', x, 'nn:', nn, 'id(x)', id(x)) or x % nn > 0
    
    
    # 3.生成器,返回下一个素数
    def primes():
        yield 2
        it = _odd_iter()  # 队列生成器
        while True:
            n = next(it)
            yield n
            it = filter(_not_divisible(n), it)
    
    
    for n in primes():
        if n < 100:
            print("---------------", n, "-------------------")
        else:
            break
    

    有几个问题
    1.我现在知道 filter(_not_divisible(n), it),这行代码是在 next(it)的时候才会真正执行,filter 过滤函数的 x 是当前 it 的值,但是 nn 为什么每次执行 filter 函数的时候 nn 一直从 3 开始递增
    2.filter 不是对序列中每一个值进行过滤函数的处理吗,那么 it 是一个惰性序列,x % nn > 0 这个退出的边界是什么啊,打印的日志 nn 递增到最后都是比 x 小,然后就退出这一次的 filter 了

    --------------- 2 -------------------
    --------------- 3 -------------------
    x: 5 nn: 3 id(x) 140728014001312
    --------------- 5 -------------------
    x: 7 nn: 3 id(x) 140728014001376
    x: 7 nn: 5 id(x) 140728014001376
    --------------- 7 -------------------
    x: 9 nn: 3 id(x) 140728014001440
    x: 11 nn: 3 id(x) 140728014001504
    x: 11 nn: 5 id(x) 140728014001504
    x: 11 nn: 7 id(x) 140728014001504
    --------------- 11 -------------------
    x: 13 nn: 3 id(x) 140728014001568
    x: 13 nn: 5 id(x) 140728014001568
    x: 13 nn: 7 id(x) 140728014001568
    x: 13 nn: 11 id(x) 140728014001568
    --------------- 13 -------------------
    x: 15 nn: 3 id(x) 140728014001632
    x: 17 nn: 3 id(x) 140728014001696
    x: 17 nn: 5 id(x) 140728014001696
    x: 17 nn: 7 id(x) 140728014001696
    x: 17 nn: 11 id(x) 140728014001696
    x: 17 nn: 13 id(x) 140728014001696
    --------------- 17 -------------------
    x: 19 nn: 3 id(x) 140728014001760
    x: 19 nn: 5 id(x) 140728014001760
    x: 19 nn: 7 id(x) 140728014001760
    x: 19 nn: 11 id(x) 140728014001760
    x: 19 nn: 13 id(x) 140728014001760
    x: 19 nn: 17 id(x) 140728014001760
    

    大神们求解啊 或者给一个方向

    5 条回复    2018-09-05 17:02:45 +08:00
    sikariba
        1
    sikariba  
       2018-09-05 15:37:54 +08:00
    1. filter 函数是在迭代你的 it,it 是_odd_iter 这个 generator,你看_odd_iter 的代码就能看出来它返回的序列是 3、5、7、9、11、13、15...2n+1
    2. 你是不是理解错了 filter 函数,filter(func,iter)是对 iter 中的每一个元素调用 func,并返回其中返回值为 true 的子元素。所以只要 x 不能被 nn 整除,就说明 x 不是质数,x 就会被返回。因为你的 it 是一个无限的奇数序列,所以它是没有所谓退出的边界的
    jmc891205
        2
    jmc891205  
       2018-09-05 15:59:14 +08:00
    1. 每一次 filter 都是在上一层 filter 外面再包一层 第一个 filter 是从 3 开始的所以每次 check 都是从 3 开始 check
    2. filter 返回的是 filter 对象 一个惰性的 filter 还是一个惰性序列
    jiaosky
        3
    jiaosky  
    OP
       2018-09-05 16:21:43 +08:00
    @sikariba 如果没有退出边界的话,那他不是应该无限的从 it 取元素去进 func 操作了么,哪为什么会打印出 3 5 7 这种算出的素数啊
    jiaosky
        4
    jiaosky  
    OP
       2018-09-05 16:40:04 +08:00
    @jmc891205 哪 filter 是怎么控制他循环的层级啊 想不通啊 蓝瘦
    sikariba
        5
    sikariba  
       2018-09-05 17:02:45 +08:00
    @jiaosky #3 如果你的 for 循环里没有那个 n<100 的判断的话,这个就是一直循环下去的。它就是遍历 3、5、7、9...这个序列,看有没有数能整除它,没有的就被 yield 返回出来了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1095 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 19:53 · PVG 03:53 · LAX 11:53 · JFK 14:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.