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
Zoeeeeecho
V2EX  ›  Python

Python 如何表示所有质数?

  •  
  •   Zoeeeeecho · 2022-09-20 00:16:35 +08:00 · 2972 次点击
    这是一个创建于 555 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刚接触 python ,作业题目要求打出输入个数的质数,格式按 10 个一行输出。我的思路是先表示出所有质数然后再按输入的个数打出质数。但我不知道如何表示所有质数。也许我的思路不对,请大家帮我看看呢,谢谢!

    第 1 条附言  ·  2022-09-20 14:54:30 +08:00
    不好意思啊大家,我的标题还有表述让大家误解我是想找素数的公式了。我最开始的想法是想问可不可以导入所有自然数然后一个一个放进判断是否为质数的函数里,然后输出所有质数,再从里面取出我想要的个数。我现在知道这是不可能的并且很幼稚的想法了,谢谢大家的评论!
    24 条回复    2022-09-21 08:46:38 +08:00
    Zoeeeeecho
        2
    Zoeeeeecho  
    OP
       2022-09-20 00:20:20 +08:00
    第一张图是题目要求,第二张图是我的代码,第三张是 output
    coderluan
        3
    coderluan  
       2022-09-20 00:30:32 +08:00
    思路错了,首先你写个函数 fun 判断数字是否是质数,然后 while 循环调用这个函数,参数从 1 开始递增,返回值是 true ,计数器+1 ,当计数器达到输入的要求,跳出循环。
    luckycat
        5
    luckycat  
       2022-09-20 00:43:19 +08:00
    能找到素数公式的话,那可是牛逼了。
    wudiiiii
        6
    wudiiiii  
       2022-09-20 00:43:37 +08:00
    首先得需要一个循环,在这个循环中不断运行函数 getBiggerPrime(x),循环结束的条件是已经得到了足够的质数。
    Zoeeeeecho
        7
    Zoeeeeecho  
    OP
       2022-09-20 00:45:32 +08:00
    @hsfzxjy 天啦,太谢谢了,苯刚学 python 第一次发帖的人狠狠感动了
    JohnBull
        8
    JohnBull  
       2022-09-20 01:10:29 +08:00
    你咋不上天呢?
    yaoyao1128
        9
    yaoyao1128  
       2022-09-20 01:11:03 +08:00 via iPhone
    关键词:筛法求素数
    yaoyao1128
        10
    yaoyao1128  
       2022-09-20 01:16:31 +08:00 via iPhone   ❤️ 1
    oi 基础算法之一,优化方式有三点,一只算奇数,二只至平方根,三减少重复
    xiri
        11
    xiri  
       2022-09-20 01:31:50 +08:00 via Android
    你这不是不会 python 的问题,是完全没有一点数学常识啊,表示出所有素数,,,,
    Zoeeeeecho
        12
    Zoeeeeecho  
    OP
       2022-09-20 01:40:20 +08:00
    @xiri 不不,我不是找规律找公式的意思,最开始是想 def 一个函数来判断所有数是否是质数而不是我输入数字来判断
    xuanbg
        13
    xuanbg  
       2022-09-20 08:18:42 +08:00
    @Zoeeeeecho 你这不是一样的么。。。输入数字的范围,通过循环一个个判断是否质数。是的话放到数组里面,完成后输出数组。
    visper
        14
    visper  
       2022-09-20 08:58:27 +08:00
    这是数学家研究的问题. 你弄个循环判断一下一个函数是不是质数然后从 2 开始要多少个打多少个就行了.
    em70
        15
    em70  
       2022-09-20 10:38:39 +08:00
    你先别管 python,现在就一张纸一支笔,你如何计算素数?如果你不知道,说明数学知识不过关,先研究数学上如何计算素数的(初中数学知识)
    krixaar
        17
    krixaar  
       2022-09-20 11:08:08 +08:00   ❤️ 1
    https://raw.githubusercontent.com/koorukuroo/Prime-Number-List/master/primes.json
    这里面有一百万个,直接 json.load ,需要几个 print 几个,超过一百万 raise 个 error 就好,性能超棒的
    MoYi123
        18
    MoYi123  
       2022-09-20 11:23:18 +08:00
    def prime(n):
    ____memo = [1 for _ in range(n)]
    ____ret = []
    ____for i in range(2, n):
    ________if memo[i]:
    ____________ret.append(i)
    ________j = 0
    ________while j < len(ret) and i * ret[j] < n:
    ____________memo[i * ret[j]] = False
    ____________if i % ret[j] == 0:
    ________________break
    ____________j += 1
    ____return ret


    欧拉筛
    haolongsun
        19
    haolongsun  
       2022-09-20 11:38:07 +08:00
    埃式筛、欧拉筛,了解一下这些数论初级算法知识。
    还有这种问题百度不更快?
    题目也是惊呆了,所有质数,你这一辈子能打印出来,就不叫菲尔兹奖了,就该以你的名字命名了。
    FYFX
        20
    FYFX  
       2022-09-20 14:14:59 +08:00
    你这个标题太吓人了,也算是 X-Y Problem 了,而且素数是无限个,这个欧几里得开始就有证明了,所以你没法表示所有的素数。不过你问题的解法就是楼上几位给出的素数筛,哦打表法也行
    filwaline
        21
    filwaline  
       2022-09-20 15:21:43 +08:00
    我来整个活,写个能生成所有质数的函数有何难(滑稽

    https://gist.github.com/filwaline/64b3f59feb819e6b337d685d55433483
    filwaline
        22
    filwaline  
       2022-09-20 15:26:32 +08:00
    #21 上一条的 gist 的质数生成器绝对是正确的

    唯一的问题是如果调用 next 取的质数太多,会触发递归太深错误(但是这是语言 /机器限制,不影响数学形式上正确)
    TimePPT
        23
    TimePPT  
       2022-09-20 16:45:07 +08:00
    def get_prime_numbers(n: int = 50):
    □□□□items = []
    □□□□i = 2
    □□□□while len(items) < n:
    □□□□□□□□if all(map(lambda x: i % x != 0, items)):
    □□□□□□□□□□□□items.append(i)
    □□□□□□□□i += 1
    □□□□return items


    def print_items(m, items):
    □□□□start = 0
    □□□□while start < len(items):
    □□□□□□□□print(items[start : start + m])
    □□□□□□□□start += m


    print_items(m=10, items=get_prime_numbers(50))
    julyclyde
        24
    julyclyde  
       2022-09-21 08:46:38 +08:00
    其实你这个想法也没啥问题,挺自然的
    直接 for 质数列表循环,每次输出一个,每 10 个换行

    关键问题是“质数列表”怎么搞。这里你可以尝试用 generator 实现,搭配 memoize decorator 减少耗时

    欧耶,可以一下子学到两个 python 特色功能了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3057 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:46 · PVG 20:46 · LAX 05:46 · JFK 08:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.