版塊導(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í)熱門版塊排行榜

返回列表

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

holmescn

金蟲 (正式寫手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時(shí)
蟲號(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ù)此樓

» 猜你喜歡

0856材料專碩353求調(diào)劑已經(jīng)有4人回復(fù)
山東省面上項(xiàng)目限額評(píng)審已經(jīng)有4人回復(fù)
一志愿北京化工大學(xué)070300 學(xué)碩336求調(diào)劑已經(jīng)有5人回復(fù)
生物學(xué)071000 329分求調(diào)劑已經(jīng)有4人回復(fù)
一志愿華中科技大學(xué)071000，求調(diào)劑已經(jīng)有4人回復(fù)
生物學(xué)一志愿985，分?jǐn)?shù)349求調(diào)劑已經(jīng)有4人回復(fù)
生物學(xué)調(diào)劑已經(jīng)有4人回復(fù)
求調(diào)劑院校信息已經(jīng)有4人回復(fù)
085600材料與化工306 已經(jīng)有4人回復(fù)
286求調(diào)劑已經(jīng)有10人回復(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 工程第三十一題: 換零錢已經(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

金蟲 (著名寫手)

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

★ ★
小木蟲(金幣+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

至尊木蟲 (著名寫手)

驃騎將軍

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

★ ★ ★ ★
小木蟲(金幣+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寫程序請(qǐng)發(fā)QQ郵件:790404545@qq.com

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

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

huycwork

金蟲 (著名寫手)

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

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

我先前說(shuō)的素?cái)?shù)算法的實(shí)現(xiàn)，偶數(shù)部分沒有優(yōu)化，效率看起來(lái)還算不錯(cuò)~第七題都沒人管了，就發(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開始會(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í)候感覺有點(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

金蟲 (正式寫手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時(shí)
蟲號(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的代碼，感覺不太好，用了goto的話，就bad smell了。我寫了一個(gè)沒有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ù)開始，選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ù)還沒有在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

金蟲 (著名寫手)

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

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

引用回帖:

Originally posted by holmescn at 2011-05-18 14:35:44:
看了huycwork的代碼，感覺不太好，用了goto的話，就bad smell了。我寫了一個(gè)沒有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í)
蟲號(hào): 0
注冊(cè): 2010-12-03
專業(yè): 動(dòng)力學(xué)與控制

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

本帖僅樓主可見

贊一下

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

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

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

返回列表

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

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

[考研] 材料學(xué)碩333求調(diào)劑 +3	北道巷 2026-03-18	3/150	2026-03-21 18:17 by 學(xué)員8dgXkO
[考研] 296求調(diào)劑 +4	www_q 2026-03-20	4/200	2026-03-21 17:26 by 學(xué)員8dgXkO
[考研] 材料與化工（0856）304求 B區(qū) 調(diào)劑 +3	邱gl 2026-03-21	3/150	2026-03-21 13:47 by lature00
[考研] 307求調(diào)劑 +3	wyyyqx 2026-03-17	3/150	2026-03-21 03:20 by JourneyLucky
[考研] 307求調(diào)劑 +10	冷笙123 2026-03-17	10/500	2026-03-21 01:54 by JourneyLucky
[考研] 材料 336 求調(diào)劑 +3	An@. 2026-03-18	4/200	2026-03-21 01:39 by JourneyLucky
[考研] 324求調(diào)劑 +5	lucky呀呀呀鴨 2026-03-20	5/250	2026-03-20 22:30 by 促天成
[考研] 288求調(diào)劑 +16	于海海海海 2026-03-19	16/800	2026-03-20 22:28 by JourneyLucky
[考研] 一志愿蘇州大學(xué)材料求調(diào)劑，總分315（英一） +5	sbdksD 2026-03-19	5/250	2026-03-20 22:10 by luoyongfeng
[考研] 329求調(diào)劑 +9	想上學(xué)吖吖 2026-03-19	9/450	2026-03-20 22:01 by luoyongfeng
[考研] 中南大學(xué)化學(xué)學(xué)碩337求調(diào)劑 +3	niko- 2026-03-19	6/300	2026-03-20 21:58 by luoyongfeng
[考研] A區(qū)線材料學(xué)調(diào)劑 +5	周周無(wú)極 2026-03-20	5/250	2026-03-20 21:33 by laoshidan
[考研] 一志愿華中農(nóng)業(yè)071010，總分320求調(diào)劑 +3	困困困困坤坤 2026-03-20	3/150	2026-03-20 20:38 by 學(xué)員8dgXkO
[考研] 08工學(xué)調(diào)劑 +5	用戶573181 2026-03-20	5/250	2026-03-20 15:47 by xia_2003
[考研] 求調(diào)劑 +3	暗涌afhb 2026-03-16	3/150	2026-03-20 00:28 by 河南大學(xué)校友
[考研] 一志愿中國(guó)海洋大學(xué)，生物學(xué)，301分，求調(diào)劑 +5	1孫悟空 2026-03-17	6/300	2026-03-19 23:46 by zcl123
[考研] 081700化工學(xué)碩調(diào)劑 +3	【1】 2026-03-16	3/150	2026-03-19 23:40 by edmund7
[考研] 326求調(diào)劑 +5	上岸的小葡 2026-03-15	6/300	2026-03-17 17:26 by ruiyingmiao
[考研] 機(jī)械專碩325，尋找調(diào)劑院校 +3	y9999 2026-03-15	5/250	2026-03-16 19:58 by y9999
[考研] 070303 總分349求調(diào)劑 +3	LJY9966 2026-03-15	5/250	2026-03-16 14:24 by xwxstudy

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

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

» 猜你喜歡

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

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

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