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

编码挑战:求一千万自然数中质数和

  •  
  •   SlipStupig · 2016-02-24 22:25:54 +08:00 · 5521 次点击
    这是一个创建于 3206 天前的主题,其中的信息可能已经有所发展或是发生改变。

    语言只能用 python ,求一千万自然数总质数总和,速度最快的有奖励哦

    第 1 条附言  ·  2016-02-25 00:54:26 +08:00
    可能我没说清楚规则,一千万不是 0-1000 万,而是自然数范围内任意一千万个数字,提交代码请注意提交一下你运行的 profile (最少也要有个运行总时间吧),测试标准环境是 i7 4700MQ 4core 4gb 内存 ddr3 1600
    35 条回复    2016-02-26 18:15:05 +08:00
    ilcwd23
        1
    ilcwd23  
       2016-02-24 22:49:18 +08:00
    打表?
    whisperzzzz
        2
    whisperzzzz  
       2016-02-24 23:05:22 +08:00
    3203324994356
    auser
        3
    auser  
       2016-02-24 23:13:10 +08:00
    速度最快的难道不是直接打印结果?
    不知道哪本书有写过哪个美国大学举办了类似比赛,然后……第一名开销是负数。
    mickeyandkaka
        4
    mickeyandkaka  
       2016-02-24 23:20:22 +08:00
    congeec
        5
    congeec  
       2016-02-24 23:35:54 +08:00   ❤️ 1
    knightdf
        6
    knightdf  
       2016-02-24 23:37:45 +08:00
    那 CPU 多的赢了,判断 2-sqrt(n)就行了
    congeec
        7
    congeec  
       2016-02-24 23:44:42 +08:00
    @auser 卡内基梅隆大学编程难题
    ianluo
        8
    ianluo  
       2016-02-24 23:49:54 +08:00 via iPhone
    @ilcwd23 神马意思?
    random2case
        9
    random2case  
       2016-02-25 00:18:49 +08:00
    private static final int MAX = 100000000;
    private static final int ARRAY_SIZE = (int) Math.round((MAX * 1.1) / Math.log(MAX));
    private static int[] array = new int[ARRAY_SIZE];
    //--//
    int pos = 0;
    array[pos++] = 2;

    int sqrtN = 3;
    int countSqrtN = 2;

    for (int i = 3; i < MAX; i += 2) {
    for (int j = 0; j < pos; j++) {
    int value = array[j];
    if (value > sqrtN) {
    premier = true;
    break;
    }
    if ((i % value) == 0) {
    premier = false;
    break;
    }
    }

    if (premier) {
    array[pos++] = i;
    }

    if (--countSqrtN == 0) {
    countSqrtN = sqrtN;
    sqrtN++;
    }
    }


    给一个 java 版的吧,暂时找不到当时 python 写的了,自己改编一下吧
    whisperzzzz
        10
    whisperzzzz  
       2016-02-25 00:22:04 +08:00
    @congeec 几个月前看这个 DP 觉得简直丧心病狂……
    whisperzzzz
        11
    whisperzzzz  
       2016-02-25 00:24:31 +08:00
    @knightdf 判断单个的话可以 Miller-Rabin ,多取几个数就好了……
    XiaoxiaoPu
        12
    XiaoxiaoPu  
       2016-02-25 00:39:34 +08:00
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>


    static inline int getbit(int *bits, int i)
    {
    return (bits[i>>5] >> (i & 31)) & 1;
    }

    static inline void setbit(int *bits, int i)
    {
    bits[i>>5] |= (1 << (i & 31));
    }

    static inline void clrbit(int *bits, int i)
    {
    bits[i>>5] &= ~(1 << (i & 31));
    }

    int isqrt(int num)
    {
    register int x1 = num, x2;

    do
    {
    x2 = x1;
    x1 = (x1 + num / x1) / 2;
    } while (x1 < x2);
    return x2;
    }


    int main()
    {
    int n = 10000000;
    int *bits;

    bits = (int *)malloc(((n>>5)+1) * sizeof(int));
    if (bits == NULL)
    {
    fprintf(stderr, "Out of memory.\n");
    return 1;
    }

    for (int i = 0; i < ((n>>5)+1); i++)
    {
    bits[i] = ~0;
    }

    clrbit(bits, 0);
    clrbit(bits, 1);
    clrbit(bits, 4);

    int end = isqrt(n);
    long sum = 0;
    for (int i = 2; i <= end; i++)
    {
    if (getbit(bits, i))
    {
    sum += i;
    int j0 = n / i;
    for (int j = 2; j <= j0; j++)
    {
    clrbit(bits, i * j);
    }
    }
    }

    printf("%ld\n", sum);

    return 0;
    }



    发个 C 写的
    ➜ ~ gcc -o prime -std=gnu99 -O3 prime.c
    ➜ ~ time ./prime
    642869
    ./prime 0.04s user 0.00s system 94% cpu 0.046 total
    ➜ ~
    XiaoxiaoPu
        13
    XiaoxiaoPu  
       2016-02-25 00:41:39 +08:00
    啊哦,上面发的错了,这个才对

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>


    static inline int getbit(int *bits, int i)
    {
    return (bits[i>>5] >> (i & 31)) & 1;
    }

    static inline void setbit(int *bits, int i)
    {
    bits[i>>5] |= (1 << (i & 31));
    }

    static inline void clrbit(int *bits, int i)
    {
    bits[i>>5] &= ~(1 << (i & 31));
    }

    int isqrt(int num)
    {
    register int x1 = num, x2;

    do
    {
    x2 = x1;
    x1 = (x1 + num / x1) / 2;
    } while (x1 < x2);
    return x2;
    }


    int main()
    {
    int n = 10000000;
    int *bits;

    bits = (int *)malloc(((n>>5)+1) * sizeof(int));
    if (bits == NULL)
    {
    fprintf(stderr, "Out of memory.\n");
    return 1;
    }

    for (int i = 0; i < ((n>>5)+1); i++)
    {
    bits[i] = ~0;
    }

    clrbit(bits, 0);
    clrbit(bits, 1);
    clrbit(bits, 4);

    int end = isqrt(n);
    for (int i = 2; i <= end; i++)
    {
    if (getbit(bits, i))
    {
    int j0 = n / i;
    for (int j = 2; j <= j0; j++)
    {
    clrbit(bits, i * j);
    }
    }
    }

    long sum = 0;
    for (int i = 2; i <= n; i++)
    {
    if (getbit(bits, i))
    {
    sum += i;
    }
    }
    printf("%ld\n", sum);

    return 0;
    }


    ➜ ~ gcc -o prime -std=gnu99 -O3 prime.c
    ➜ ~ ./prime
    3203324994356
    ➜ ~
    msg7086
        14
    msg7086  
       2016-02-25 03:46:02 +08:00
    好没挑战啊。某节大二课后作业就是用 pthread 做并行筛法求质数, INTMAX 之内的所有质数,最后求总数。这个改成求和也并不难,把统计时候的 cnt++ 改成 sum+=x 就行了。
    msg7086
        15
    msg7086  
       2016-02-25 03:50:49 +08:00
    另外这题目也太不规范了。比如「自然数范围内任意一千万个数字」,自然数范围大了,难道要支持几万位的数字?
    sinxccc
        16
    sinxccc  
       2016-02-25 04:19:32 +08:00
    @auser "Expert C Programming: Deep C Secrets" 里的段子。
    SlipStupig
        17
    SlipStupig  
    OP
       2016-02-25 08:13:54 +08:00
    @msg7086 大整数加减有何不可,你代码够优秀放出来
    em70
        18
    em70  
       2016-02-25 08:53:02 +08:00 via iPhone
    任意 1000 万个数字,不一定是连续的数字吧,不一定没有重复吧,也就是说是包含 1000 万个无规律数字的数组中求质数总和?
    SlipStupig
        19
    SlipStupig  
    OP
       2016-02-25 09:04:56 +08:00
    @em70 很正确
    knightdf
        20
    knightdf  
       2016-02-25 09:17:11 +08:00
    @whisperzzzz 这个好像是更专业
    linux40
        21
    linux40  
       2016-02-25 10:21:13 +08:00 via Android
    。。。这个问题难道不是在常数时间么。。。
    mulog
        22
    mulog  
       2016-02-25 10:35:08 +08:00
    太不严谨了吧 连个范围都没有。
    「任意自然数中质数和」?你能把所有自然数中的质数都找出来吗?
    目前已知最大质数是 2^74207281 ,有那个本事先找出个更大的上上新闻联播再说。。
    odirus
        23
    odirus  
       2016-02-25 10:39:44 +08:00
    我觉得如果要比赛,至少你要先确定范围撒,还要有相同的运行环境撒。。。我去哪里找 "i7 4700MQ 4core 4gb 内存 ddr3 1600" 这种环境?
    slixurd
        24
    slixurd  
       2016-02-25 11:13:46 +08:00
    https://leetcode.com/problems/count-primes/
    你们可以试试在 leetcode 上做下,虽然题目不完全一样。
    如果你的答案能比 90%以上的人快,才说明你做得好,如果用它 hint 的方法或者暴力求解,速度不会快的。
    Hello1995
        25
    Hello1995  
       2016-02-25 12:07:26 +08:00 via Android
    @mulog 2^74207281 显然不是素数。
    mulog
        26
    mulog  
       2016-02-25 12:21:49 +08:00
    @Hello1995
    哈哈哈哈 对
    2^74207281 - 1
    JayXon
        27
    JayXon  
       2016-02-25 12:37:37 +08:00
    @slixurd 那个题 test case 太简单,根本比不出什么,我的代码跑出来是 0 ms
    slixurd
        28
    slixurd  
       2016-02-25 13:36:47 +08:00
    @JayXon 啊对,那的 testcase 太弱
    话说你该不会是做 Thunder JayXon 版的那个 JayXon 吧
    msg7086
        29
    msg7086  
       2016-02-25 13:48:48 +08:00
    @SlipStupig 题目都没出明白还要人做么。
    别说乱取一千万个数,我就取这一千万个数的个位和十位,连在一起组成一个两千万位的数,你要跑多久?
    已知 22 楼那个大数有 2234 万位,拿 i7 不间断跑了 31 天。
    来吧,不管你代码优秀不优秀,都可以放出来,我们来看看半年能不能跑完?
    Xs0ul
        30
    Xs0ul  
       2016-02-25 13:50:01 +08:00
    @mulog 你说的那是最大的梅森素数,并不是最大的素数
    mulog
        31
    mulog  
       2016-02-25 14:19:56 +08:00
    @Xs0ul
    咦 google 出来几个源都说是这个数 那请问现在已知最大的素数是多少?
    Xs0ul
        32
    Xs0ul  
       2016-02-25 17:18:24 +08:00
    @mulog 我建议你搜下“梅森素数”
    brbrarts
        33
    brbrarts  
       2016-02-26 12:55:48 +08:00
    @Xs0ul 2^74207281-1 是最大的梅森素数,同时也是最大的已知素数

    我觉得梅森素数另外还有一个优势,就是表达很简洁。 2^74207281-1 写出来有两千多万位,假设有一个更大的素数,并且他不能用这种简洁的方式表现出来,那你怎么告诉别人这个数是多少呢?在贴子里贴两千多万位数字么。。。
    JayXon
        34
    JayXon  
       2016-02-26 16:20:20 +08:00
    @slixurd 是啊
    slixurd
        35
    slixurd  
       2016-02-26 18:15:05 +08:00
    @JayXon 遇到大神了
    记得三四年前基本上都是用你迅雷修改版的
    直到后来上了 Linux.....
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4826 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:01 · PVG 12:01 · LAX 20:01 · JFK 23:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.