版塊導(dǎo)航: 正在加載中...

應(yīng)《網(wǎng)絡(luò)安全法》要求，自2017年10月1日起，未進(jìn)行實(shí)名認(rèn)證將不得使用互聯(lián)網(wǎng)跟帖服務(wù)。為保障您的帳號(hào)能夠正常使用，請(qǐng)盡快對(duì)帳號(hào)進(jìn)行手機(jī)號(hào)驗(yàn)證，感謝您的理解與支持！

24小時(shí)熱門(mén)版塊排行榜

返回列表

本帖產(chǎn)生 3 個(gè) 程序強(qiáng)帖，點(diǎn)擊這里進(jìn)行查看

holmescn

金蟲(chóng) (正式寫(xiě)手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時(shí)
蟲(chóng)號(hào): 913482
注冊(cè): 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

[交流] Euler 工程第十題：計(jì)算小于2百萬(wàn)的所有質(zhì)數(shù)的和已有3人參與

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

小于10的所有質(zhì)數(shù)的和為：2+3+5+7 = 17

那么小于2百萬(wàn)的所有質(zhì)數(shù)的和是多少？

PS：最近的關(guān)于質(zhì)數(shù)的問(wèn)題還真是多啊，哈哈。
PS2：到第10題了，這個(gè)題的解出率已經(jīng)是第一題的一半還不到了。

回復(fù)此樓

» 猜你喜歡

一志愿東華大學(xué)化學(xué)070300，求調(diào)劑已經(jīng)有8人回復(fù)
277材料科學(xué)與工程080500求調(diào)劑已經(jīng)有7人回復(fù)
317求調(diào)劑已經(jīng)有18人回復(fù)
293求調(diào)劑已經(jīng)有5人回復(fù)
280分求調(diào)劑一志愿085802 已經(jīng)有7人回復(fù)
0854電子信息求調(diào)劑已經(jīng)有3人回復(fù)
263求調(diào)劑已經(jīng)有4人回復(fù)
石河子大學(xué)（211、雙一流）碩博研究生長(zhǎng)期招生公告已經(jīng)有3人回復(fù)
一志愿西安交通大學(xué)材料工程專業(yè) 282分求調(diào)劑已經(jīng)有13人回復(fù)
北科281學(xué)碩材料求調(diào)劑已經(jīng)有6人回復(fù)

» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:

Euler 工程第四十四題已經(jīng)有4人回復(fù)
Euler 工程第四十二題: 三角詞已經(jīng)有4人回復(fù)
Euler 工程第四十一題已經(jīng)有5人回復(fù)
Euler 工程第三十八題已經(jīng)有9人回復(fù)
Euler 工程第三十七題已經(jīng)有6人回復(fù)
Euler 工程第三十六題：已經(jīng)有18人回復(fù)
Euler 工程第三十五題：循環(huán)質(zhì)數(shù) 已經(jīng)有16人回復(fù)
Euler 工程第三十二題：pandigital 數(shù) 已經(jīng)有3人回復(fù)
Euler 工程第三十一題: 換零錢(qián) 已經(jīng)有10人回復(fù)
Euler 工程第三十題已經(jīng)有12人回復(fù)
Euler 工程第廿九題：有多少不同的項(xiàng)? 已經(jīng)有30人回復(fù)
Euler 工程第廿八題：旋轉(zhuǎn)矩陣對(duì)角線的和已經(jīng)有6人回復(fù)
Euler 工程第廿七題：系數(shù)的積已經(jīng)有15人回復(fù)
Euler 工程第廿六題：最長(zhǎng)的循環(huán)節(jié) 已經(jīng)有9人回復(fù)
Euler 工程第廿五題：Fibonacci 數(shù)列第一個(gè)包含1000個(gè)數(shù)字的項(xiàng) 已經(jīng)有3人回復(fù)
Euler 工程第廿四題：全排列的第100萬(wàn)項(xiàng) 已經(jīng)有19人回復(fù)
Euler 工程第廿三題：已經(jīng)有16人回復(fù)
Euler 工程第廿二題: 姓的總分已經(jīng)有13人回復(fù)
Euler 工程第廿題：100! 的各項(xiàng)和已經(jīng)有5人回復(fù)
Euler 工程第十九題：每月第一天是周日的天數(shù) 已經(jīng)有4人回復(fù)
Euler 工程第十八題：三角陣上最大的和已經(jīng)有12人回復(fù)
Euler 工程第十六題：2的1000次方的各項(xiàng)和已經(jīng)有14人回復(fù)
Euler 工程第14題：找最長(zhǎng)的數(shù)列已經(jīng)有9人回復(fù)
Euler 工程第十一題：相鄰元素乘積最大已經(jīng)有10人回復(fù)
Euler 工程第三題：尋找600851475143的最大質(zhì)因子已經(jīng)有18人回復(fù)

1樓 2011-05-15 08:14:34

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲(chóng) (著名寫(xiě)手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時(shí)
蟲(chóng)號(hào): 1257243
注冊(cè): 2011-04-06
專業(yè): 金融學(xué)

★ ★
小木蟲(chóng)(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+1): 謝謝參與討論！ 2011-05-15 19:21:06

只是這些質(zhì)數(shù)問(wèn)題，側(cè)重點(diǎn)各有不同，第三題要求找出最大質(zhì)數(shù)，第七題要求解出第10001個(gè)質(zhì)數(shù)，而這一題根本不要求測(cè)試出所有質(zhì)數(shù)，只是求和而已，解法應(yīng)該也有特殊之處。

贊一下(2人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

2樓2011-05-15 08:44:32

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲(chóng) (著名寫(xiě)手)

驃騎將軍

程序強(qiáng)帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時(shí)
蟲(chóng)號(hào): 696514
注冊(cè): 2009-02-05
專業(yè): 計(jì)算機(jī)軟件

★ ★ ★ ★
小木蟲(chóng)(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+3): 謝謝參與交流！ 2011-05-15 19:21:33

還是老規(guī)矩,先來(lái)個(gè)偷懶的解法

CODE:

function result = euler10()

tic;

result = sum(primes(2000000));

toc;

end

結(jié)果+運(yùn)行時(shí)間

CODE:

 % Elapsed time is 0.087248 seconds.

% ans =

%               142913828922

贊一下(2人)

回復(fù)此樓

matlab/VB/python/c++/Java寫(xiě)程序請(qǐng)發(fā)QQ郵件:790404545@qq.com

3樓2011-05-15 14:56:17

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲(chóng) (著名寫(xiě)手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時(shí)
蟲(chóng)號(hào): 1257243
注冊(cè): 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★ ★
小木蟲(chóng)(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+3, 程序強(qiáng)帖+1): 謝謝參與交流！ 2011-05-15 19:21:47

我先前說(shuō)的素?cái)?shù)算法的實(shí)現(xiàn)，偶數(shù)部分沒(méi)有優(yōu)化，效率看起來(lái)還算不錯(cuò)~第七題都沒(méi)人管了，就發(fā)這吧：

CODE:

#include 

#include 

using namespace std;

enum {

        BUFSZ = 10000,//這個(gè)限制產(chǎn)生性能瓶頸，設(shè)置越大，性能就越好

        NPRI = 10001    //這個(gè)數(shù)據(jù)就需要估計(jì)了，不想估計(jì)，就直接vector吧:)

};

bool buf[BUFSZ];

size_t primer[NPRI];

size_t eular7(size_t nprimer = 10001){

        size_t offset = 0, *prip, *cprip;

        int top;//記錄素?cái)?shù)數(shù)

        int falc;//排除的數(shù)

        bool *bufp;

        primer[0] = 2;//負(fù)責(zé)偶數(shù)部分

        primer[1] = 3;

        primer[2] = 5;

        top = 3;

        //如果從1開(kāi)始會(huì)把所有的數(shù)都false了，offset必須比1要大

        offset += 5;

        while(1){

                for(size_t i = 0; i < BUFSZ; ++i)

                        buf[i] = true;

                falc = 0;

                prip = primer;

                cprip = primer + top;

                bufp = buf;

NEWPRI:   //每當(dāng)有新的素?cái)?shù)就跳回來(lái)

                //檢查每個(gè)已知的素?cái)?shù)，這部分可能有bug，測(cè)試的時(shí)候感覺(jué)有點(diǎn)問(wèn)題

                while(prip - primer < top){

                        size_t mod = offset%(*prip);

                        if(mod == 0){

                                buf[0] = false;

                                ++falc;

                        }

                        for(size_t i = *prip - mod; i < BUFSZ; i+=*prip){

                                if(buf[i])

                                        ++falc;

                                buf[i] = false;

                        }

                        ++prip;//這個(gè)指針保證，不會(huì)重復(fù)遍歷素?cái)?shù)表

                }

                //添加未知的素?cái)?shù)，每次只添加一個(gè)

                for(int i = bufp - buf; i < BUFSZ; ++i){

                        if(buf[i]){

                                primer[top++] = offset + i;

                                if(top == nprimer)

                                        goto DONE;

                                bufp = buf+i;//這個(gè)指針保證，不會(huì)重復(fù)檢查緩沖數(shù)表

                                if(falc + prip - cprip < BUFSZ)

                                        goto NEWPRI;

                        }

                }

                offset += BUFSZ;

        }

DONE:

        return primer[nprimer-1];

}

int main(){

        time_t t1, t2;

        t1 = time(0);

        size_t res = eular7();

        t2 = time(0);

        cout<<"result:"<
        cout<<"cost:"<
        return 0;

}

如果要適應(yīng)這題，修改終止條件即可。

贊一下(2人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

4樓2011-05-15 15:45:50

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

holmescn

金蟲(chóng) (正式寫(xiě)手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時(shí)
蟲(chóng)號(hào): 913482
注冊(cè): 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

★ ★
余澤成(金幣+2, 程序強(qiáng)帖+1): 謝謝參與交流！ 2011-05-18 17:05:42

看了huycwork的代碼，感覺(jué)不太好，用了goto的話，就bad smell了。我寫(xiě)了一個(gè)沒(méi)有g(shù)oto的版本不過(guò)，可能有地方會(huì)重疊，造成速度慢。

CODE:

#include

#include

#include

#define PRIMESZ 100002

#define BUFSZ 10000

int nthPrime(int nth) {

    // 總共的質(zhì)數(shù)集

    int primes[PRIMESZ];

    // 每次過(guò)濾用的buffer

    int buf[BUFSZ];

    // 已知的質(zhì)數(shù)個(gè)數(shù)

    int amountOfPrimes;

    // 記錄buffer的第一個(gè)數(shù)

    // 最后一個(gè)數(shù)以及下一個(gè)

    // 是當(dāng)前質(zhì)數(shù)的倍數(shù)的數(shù)

    int next, first, last;

    int i, j;

    // 先給兩個(gè)質(zhì)數(shù)

    primes[0] = 2;

    primes[1] = 3;

    amountOfPrimes = 2;

    last = 3;

    while (amountOfPrimes < nth) {

        // 填充buffer, 不要偶數(shù)

        // 這里從最大質(zhì)數(shù)開(kāi)始，選BUFSZ個(gè)數(shù)

        // 可能有些數(shù)會(huì)被重復(fù)查找

        // 但可以防止漏掉數(shù)

        for(i = 0; i < BUFSZ; i++) {

            buf[i] = primes[amountOfPrimes - 1] + i*2;

        }

        // 保存第一個(gè)數(shù)和最后一個(gè)數(shù)，因?yàn)榭赡鼙恍薷?br />
        first = buf[0];

        last  = buf[BUFSZ-1];

        for(i = 1; i < amountOfPrimes; i++) {

            // 下一個(gè)大于first但是primes[i]的倍數(shù)的數(shù)

            next = ceil(first * 1.0 / primes[i]);

            // 防止得到偶數(shù)

            if (next % 2 == 0) next += 1;

            // 過(guò)濾掉primes[i]的倍數(shù)

            // 這里我想了很久......

            // 主要是腦子不夠用

            for(j = next * primes[i]; j <= last; j += primes[i]*2) {

                buf[(j - first)/2] = 0;

            }

        }

        // 把過(guò)濾完了的質(zhì)數(shù)加到primes里

        // 不能加得太多，因?yàn)榭赡苡行┵|(zhì)數(shù)還沒(méi)有在primes里

        // 這些質(zhì)數(shù)的倍數(shù)可能會(huì)被加進(jìn)來(lái)

        for(j = 0; j < (BUFSZ < amountOfPrimes?BUFSZ:amountOfPrimes); j++) {

            if(buf[j]) {

                primes[amountOfPrimes++] = buf[j];

            }

            // 夠數(shù)了就別再加了

            if(amountOfPrimes > PRIMESZ)

                break;

        }

    }

    return primes[nth-1];

}

int main(int argc, char** argv){

    time_t t;

    t = time(0);

    printf("nthPrimes = %d\n", nthPrime(100001));

    printf("%d\n", time(0)-t);

    return 0;

}

贊一下(1人)

回復(fù)此樓

5樓2011-05-18 14:35:44

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲(chóng) (著名寫(xiě)手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時(shí)
蟲(chóng)號(hào): 1257243
注冊(cè): 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★
小木蟲(chóng)(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+2): 鼓勵(lì)交流！ 2011-05-18 17:06:02

引用回帖:

Originally posted by holmescn at 2011-05-18 14:35:44:
看了huycwork的代碼，感覺(jué)不太好，用了goto的話，就bad smell了。我寫(xiě)了一個(gè)沒(méi)有g(shù)oto的版本不過(guò)，可能有地方會(huì)重疊，造成速度慢。

[code]
#include<stdio.h>
#include<math.h>
#include<tim ...

呃，不要goto的版本只需要用return替換掉第一個(gè)goto，把while拷貝到第二個(gè)goto即可，不過(guò)，代碼看起來(lái)可能更bad誒……

贊一下(2人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

6樓2011-05-18 15:01:27

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

匿名

用戶注銷 (小有名氣)

程序強(qiáng)帖: 3
應(yīng)助: 2 (幼兒園)
金幣: 607.7
散金: 150
紅花: 2
帖子: 195
在線: 104小時(shí)
蟲(chóng)號(hào): 0
注冊(cè): 2010-12-03
專業(yè): 動(dòng)力學(xué)與控制

★ ★ ★ ★
小木蟲(chóng)(金幣+0.5):給個(gè)紅包，謝謝回帖
余澤成(金幣+3, 程序強(qiáng)帖+1): 鼓勵(lì)參與交流！ 2011-05-24 12:38:22

本帖僅樓主可見(jiàn)

贊一下

7樓2011-05-24 09:58:17

已閱回復(fù)此樓編輯查看我的主頁(yè)

相關(guān)版塊跳轉(zhuǎn) 我要訂閱樓主 holmescn 的主題更新

返回列表

普通表情龍兔虎貓高級(jí)回復(fù) (可上傳附件)

最具人氣熱帖推薦 [查看全部]		作者	回/看	最后發(fā)表

[考研] 317求調(diào)劑 +12	申子申申 2026-03-19	18/900	2026-03-22 22:23 by luoyongfeng
[考研] 298求調(diào)劑 +6	上岸6666@ 2026-03-20	6/300	2026-03-22 20:21 by edmund7
[考研] 306求調(diào)劑 +5	來(lái)好運(yùn)來(lái)來(lái)來(lái) 2026-03-22	5/250	2026-03-22 16:17 by BruceLiu320
[考研] 070300化學(xué)求調(diào)劑 +3	苑豆豆 2026-03-20	3/150	2026-03-22 14:48 by ColorlessPI
[考研] 一志愿北京化工大學(xué)070300 學(xué)碩336求調(diào)劑 +5	vv迷 2026-03-21	8/400	2026-03-22 14:20 by ColorlessPI
[考研] 297求調(diào)劑 +11	戲精丹丹丹 2026-03-17	12/600	2026-03-21 17:47 by ColorlessPI
[考研] 296求調(diào)劑 +4	www_q 2026-03-20	4/200	2026-03-21 17:26 by 學(xué)員8dgXkO
[考研] 279求調(diào)劑 +5	紅衣隱官 2026-03-21	5/250	2026-03-21 14:59 by lature00
[考研] 265求調(diào)劑 +12	梁梁校校 2026-03-19	14/700	2026-03-21 13:38 by lature00
[考研] 材料學(xué)學(xué)碩080502 337求調(diào)劑-一志愿華中科技大學(xué) +4	順順順mr 2026-03-18	5/250	2026-03-21 10:22 by luoyongfeng
[考研] 265求調(diào)劑 +3	Jack?k?y 2026-03-17	3/150	2026-03-21 03:17 by JourneyLucky
[考研] 材料專碩英一數(shù)二306 +7	z1z2z3879 2026-03-18	7/350	2026-03-20 23:48 by JourneyLucky
[考研] 一志愿中海洋材料工程專碩330分求調(diào)劑 +8	小材化本科 2026-03-18	8/400	2026-03-20 23:16 by JourneyLucky
[考研] 材料與化工 322求調(diào)劑 +4	然11 2026-03-19	4/200	2026-03-20 22:12 by luoyongfeng
[考研] 320求調(diào)劑0856 +3	不想起名字112 2026-03-19	3/150	2026-03-19 22:53 by 學(xué)員8dgXkO
[考研] 085601材料工程專碩求調(diào)劑 +10	慕寒mio 2026-03-16	10/500	2026-03-19 15:26 by 丁丁*
[考研] 材料與化工求調(diào)劑 +7	為學(xué)666 2026-03-16	7/350	2026-03-19 14:48 by 盡舜堯1
[考研] 328求調(diào)劑，英語(yǔ)六級(jí)551，有科研經(jīng)歷 +4	生物工程調(diào)劑 2026-03-16	12/600	2026-03-19 11:10 by 生物工程調(diào)劑
[考研] 【同濟(jì)軟件】軟件（085405）考研求調(diào)劑 +3	2026eternal 2026-03-18	3/150	2026-03-18 19:09 by 搏擊518
[考研] 333求調(diào)劑 +3	文思客 2026-03-16	7/350	2026-03-16 18:21 by 文思客

24小時(shí)熱門(mén)版塊排行榜

[交流] Euler 工程 第十題：計(jì)算小于2百萬(wàn)的所有質(zhì)數(shù)的和 已有3人參與

» 猜你喜歡

» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:

[交流] Euler 工程第十題：計(jì)算小于2百萬(wàn)的所有質(zhì)數(shù)的和已有3人參與

» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助: