版塊導航: 正在加載中...

登錄注冊

應《網絡安全法》要求，自2017年10月1日起，未進行實名認證將不得使用互聯(lián)網跟帖服務。為保障您的帳號能夠正常使用，請盡快對帳號進行手機號驗證，感謝您的理解與支持！

24小時熱門版塊排行榜

返回列表

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

[交流] Euler 工程第廿七題：系數的積已有4人參與

Euler大牛給出了一個很牛的二次公式:

引用回帖:

n^2 + n + 41

這個很牛的公式, 當n 從0取到39的時候,能給出40個質數. 可是當n=40的時候,就失靈了.

使用計算機, 我們又得到一個更牛的公式

引用回帖:

n^2 - 79n + 1601

這哥們,當n從0取到79的時候,能給出80個質數.

如果我們定義這樣的一個二次公式: n^2 + an + b
a 和 b 的絕對值都小于1000, 當這個公式能產生最多的質數的時候, 給出a和b的積.

致歉：
開始譯的時候，我理解錯了，結果給出錯誤的表述，讓大家產生了誤解，在這里說聲對不起了。

[ Last edited by holmescn on 2011-6-16 at 19:54 ]

回復此樓

» 猜你喜歡

1樓 2011-06-16 09:35:42

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

sudo

木蟲 (正式寫手)

程序強帖: 16
應助: 6 (幼兒園)
金幣: 1297.6
散金: 1486
紅花: 20
帖子: 588
在線: 641小時
蟲號: 1211394
注冊: 2011-02-24
性別: GG
專業(yè): 文藝美學

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+3): 鼓勵交流！ 2011-06-18 16:07:37

“產生最多的質數”這個說法有點模糊呢，看例子，是不是指n從0開始取，然后遞增1，直到式子n^2 + an + b不再為質數為止，這個過程中n的個數呢？

然后那個80個質數的例子是暗示一個上限嗎

：

80^2 + 1000*80 + 1000 = 87400 （使用的質數表中，最大的質數小于這個數~）

贊一下(2人)

回復此樓

2樓2011-06-16 10:43:17

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

huycwork

金蟲 (著名寫手)

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

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+3): 鼓勵交流！ 2011-06-18 16:07:47

引用回帖:

Originally posted by sudo at 2011-06-16 10:43:17:
“產生最多的質數”這個說法有點模糊呢，看例子，是不是指n從0開始取，然后遞增1，直到式子n^2 + an + b不再為質數為止，這個過程中n的個數呢？

然后那個80個質數的例子是暗示一個上限嗎

：

80^2 + 1000*8 ...

應該是沒有什么暗示的吧。要找的是從[0~x)自然數區(qū)間映射到素數空間的一個函數映射f(n)=n(n+a)+b，要求0~x這個區(qū)間最長。

a取正數的時候n+a肯定不能超過b，x的取值就是0~(b-a)，a取負數的時候似乎只能達到|a|，函數形狀是對稱的，能到達|a|純屬巧合，真正的產生素數的部分是0~|a/2|這個部分，x所在的區(qū)間應該是0~|a|。不過再往下也不是沒可能，最可靠的估計還是0~b。

a的搜索區(qū)間是-1000~1000，b的搜索區(qū)間則是0~1000內的素數，算法看起來需要O(n*n/Inn)的復雜度，多項式時間可解的搜索問題吧。

[ Last edited by huycwork on 2011-6-16 at 12:26 ]

贊一下(2人)

回復此樓

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

3樓2011-06-16 11:50:23

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

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強帖: 40
應助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計算機軟件

★ ★ ★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+5): 鼓勵交流！ 2011-06-18 16:08:02

這個只能暴力解吧,

CODE:

 #include 

#include 

#include 

bool isPrime(int n)

{

        int i;

        bool flag = true;

        for(i=2;i
        {

                if(n%i==0)

                {

                        flag = false;

                        break;

                }

        }

        return flag;

}

int main(int args,char* argv[])

{

        int a=0,b=0,i,j;

        int maxlen=0, curlen,n;

        for(i=-999;i<1000;i++)

        {

                for(j=-999;j<1000;j++)

                {

                        if(!isPrime(j)) // n^2+a*n+b, b must be a prime while n==0

                                continue;

                        curlen = 1; // n==0

                        for(n=1;n<79;n++)

                        {

                                if(!isPrime(n*n+i*n+j))

                                        break;

                                curlen += 1;

                        }

                        if(curlen>maxlen)

                        {

                                maxlen = curlen;

                                a = i;

                                b = j;

                        }

                }

        }

        printf("While %d*%d=%d, (n^2+(%d)*n+%d) produces %d primes.\n",a,b,a*b,a,b,maxlen);

        return 0;

}

結果

CODE:

 % While -61*971=-59231, (n^2+(-61)*n+971) produces 72 primes.

% Elapsed time is 1.578 seconds.

[ Last edited by libralibra on 2011-6-16 at 16:46 ]

贊一下(2人)

回復此樓

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

4樓2011-06-16 16:23:25

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

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

★ ★ ★
余澤成(金幣+3): 鼓勵交流！ 2011-06-18 16:08:15

我還以為表達清楚了呢. 其實就是n從0取到m,這m+1個數都是質數.然后看a*b等于多少.

Matlab版的窮舉法:

CODE:

tic

maxn = 0;

maxp = [0 0];

for a = -1000:1000

    for b = -1000:1000

        n = 0;

        while (n^2 + a*n + b) > 0 && isprime(n^2 + a*n +b)

            n = n + 1;

        end

        if n > maxn

            maxn = n;

            maxp = [a b];

            fprintf('maxn=%d\n', maxn);

        end

    end

end

fprintf('a=%d,b=%d, a*b=%d\n', maxp(1), maxp(2), maxp(1)*maxp(2));

toc

結果:

引用回帖:

a = -61, b = 971, a*b = -59231
用時 150 秒. 共有72個質數

[ Last edited by holmescn on 2011-6-16 at 16:37 ]

贊一下(1人)

回復此樓

5樓2011-06-16 16:36:15

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

huycwork

金蟲 (著名寫手)

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

★
小木蟲(金幣+0.5):給個紅包，謝謝回帖

引用回帖:

：

80^2 + 1000*8 ...

很高的洞察力哈~佩服佩服~

閣下莫非是根據1601超過1000判斷這個上限的？

贊一下(1人)

回復此樓

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

6樓2011-06-16 16:49:20

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

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

★ ★
余澤成(金幣+2): 辛苦了！ 2011-06-18 16:08:40

修改以后, 假設b是質數,這樣時間變成原來的三分之一了

CODE:

tic

bprime = primes(1000);

maxn = 0;

maxp = [0 0];

for a = -1000:1000

    for i = 1:length(bprime)

        n = 0;

        b = bprime(i);

        while (n^2 + a*n + b) > 0 && isprime(n^2 + a*n +b)

            n = n + 1;

        end

        if n > maxn

            maxn = n;

            maxp = [a b];

        end

    end

end

fprintf('a=%d,b=%d, a*b=%d\n', maxp(1), maxp(2), maxp(1)*maxp(2));

toc

贊一下(1人)

回復此樓

7樓2011-06-16 16:50:45

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

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

引用回帖:

Originally posted by libralibra at 2011-06-16 16:23:25:
這個只能暴力解吧,

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

bool isPrime(int n)
{
int i;
bool flag = true;
for(i=2;i<sqrt(abs(n));i++)
{
...

如果先給b生成一個質數表呢, 我想還能再快, 可能不到1秒了.

贊一下

回復此樓

8樓2011-06-16 16:55:23

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

fatpig8832

鐵桿木蟲 (著名寫手)

應助: 16 (小學生)
金幣: 7420.2
散金: 31
紅花: 28
帖子: 1438
在線: 610.9小時
蟲號: 770403
注冊: 2009-05-14

★
小木蟲(金幣+0.5):給個紅包，謝謝回帖

汗，題目寫得太令人費解了...

n^2 + n + 41 能給出前40個質數

我還以為是指從2開始的40個質數呢...后來一看不是，原來是從41開始的40個質數...后來一看又不是，原來，是指 n^2 + n + 41 這條公式給出的前40個解都是質數...

贊一下(1人)

回復此樓

9樓2011-06-16 17:35:39

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

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強帖: 40
應助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計算機軟件

★
小木蟲(金幣+0.5):給個紅包，謝謝回帖

引用回帖:

Originally posted by fatpig8832 at 2011-06-16 17:35:39:
汗，題目寫得太令人費解了...

n^2 + n + 41 能給出前40個質數

我還以為是指從2開始的40個質數呢...后來一看不是，原來是從41開始的40個質數...后來一看又不是，原來，是指 n^2 + n + 41 這條公式給出的前40 ...

哈哈,這個題目英文說明很清楚的,

Euler published the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

贊一下(1人)

回復此樓

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

10樓2011-06-16 17:41:39

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

相關版塊跳轉我要訂閱樓主 holmescn 的主題更新

返回列表

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

[考研] 281求調劑（0805） +6	煙汐憶海 2026-03-16	16/800	2026-03-19 00:59 by 煙汐憶海
[考研] 材料工程專碩調劑 +5	204818@lcx 2026-03-17	6/300	2026-03-18 22:55 by 204818@lcx
[考研] 267一志愿南京工業(yè)大學0817化工求調劑 +8	SUICHILD 2026-03-12	8/400	2026-03-18 20:55 by winsuccess
[考研] 070303一志愿西北大學學碩310找調劑 +6	d如愿上岸 2026-03-12	9/450	2026-03-18 19:50 by macy2011
[考研] 266求調劑 +5	陽陽哇塞 2026-03-14	9/450	2026-03-18 15:05 by stone_128
[考研] 0703化學調劑 +4	pupcoco 2026-03-17	7/350	2026-03-18 12:14 by djl2006
[考研] 0703化學求調劑總分331 +3	ZY-05 2026-03-13	3/150	2026-03-18 10:58 by macy2011
[考研] 材料，紡織，生物（0856、0710），化學招生啦 +3	Eember. 2026-03-17	9/450	2026-03-18 10:28 by Eember.
[考研] 301求調劑 +4	A_JiXing 2026-03-16	4/200	2026-03-17 17:32 by ruiyingmiao
[考研] 085601求調劑 +4	Du.11 2026-03-16	4/200	2026-03-17 17:08 by ruiyingmiao
[考研] 085600材料與化工求調劑 +5	緒幸與子 2026-03-17	5/250	2026-03-17 16:40 by laoshidan
[考研] 一志愿南京大學，080500材料科學與工程，調劑 +4	Jy? 2026-03-16	4/200	2026-03-17 11:02 by gaoqiong
[考研] 283求調劑 +3	聽風就是雨； 2026-03-16	3/150	2026-03-17 07:41 by 熱情沙漠
[考研] [導師推薦]西南科技大學國防/材料導師推薦 +3	尖角小荷 2026-03-16	6/300	2026-03-16 23:21 by 尖角小荷
[考研] 0703 物理化學調劑 +3	我可以上岸的對?/a> 2026-03-13	5/250	2026-03-16 10:50 by 我可以上岸的對?/a>
[考研] 327求調劑 +6	拾光任染 2026-03-15	11/550	2026-03-15 22:47 by 拾光任染
[考研] 中科大材料與化工319求調劑 +3	孟鑫材料 2026-03-14	3/150	2026-03-14 20:10 by ms629
[考研] 0856材料與化工301求調劑 +5	奕束光 2026-03-13	5/250	2026-03-13 22:00 by 星空星月
[碩博家園] 085600 260分求調劑 +3	天空還下雨么 2026-03-13	5/250	2026-03-13 18:46 by 天空還下雨么
[考研] 333求調劑 +3	152697 2026-03-12	4/200	2026-03-13 07:08 by Iveryant

24小時熱門版塊排行榜

[交流] Euler 工程 第廿七題：系數的積 已有4人參與

» 猜你喜歡

[交流] Euler 工程第廿七題：系數的積已有4人參與