应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

Znn3bq.jpeg
小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿七题：系数的积
51/1返回列表
查看: 1495  |  回复: 15
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

holmescn

金虫 (正式写手)

[交流] 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发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★
小木虫(金币+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写程序请发QQ邮件:790404545@qq.com
10楼2011-06-16 17:41:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 16 个回答

sudo

木虫 (正式写手)
★ ★ ★ ★
小木虫(金币+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发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★ ★
小木虫(金币+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)自然数区间映射到素数空间的一个函数映射f(n)=n(n+a)+b，要求0~x这个区间最长。

a取正数的时候n+a肯定不能超过b，x的取值就是0~(b-a)，a取负数的时候似乎只能达到|a|，函数形状是对称的，能到达|a|纯属巧合，真正的产生素数的部分是0~|a/2|这个部分，x所在的区间应该是0~|a|。不过再往下也不是没可能，最可靠的估计还是0~b。

a的搜索区间是-1000~1000，b的搜索区间则是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发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★ ★ ★
小木虫(金币+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写程序请发QQ邮件:790404545@qq.com
4楼2011-06-16 16:23:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 16 个回答
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 085600材料与化工调剂 5+3 孜孜不倦2002 2026-04-19 6/300 2026-04-20 21:25 by babero
[考研] 320求调剂 +6 深郊akm 2026-04-17 6/300 2026-04-20 18:57 by fs26jie
[论文投稿] 期刊推荐 +3 材料研究生 2026-04-15 5/250 2026-04-20 16:02 by 豆豆7758
[论文投稿] 有没有接收比较快的sci期刊呀，最好在一个月之内的，研三孩子求毕业 20+4 之护着 2026-04-16 7/350 2026-04-20 15:45 by 豆豆7758
[教师之家] 又一批高校组建人工智能学院 师资行吗 不是骗人吗 +4 yexuqing 2026-04-19 4/200 2026-04-20 14:47 by brantleo
[考博] 湖南大学刘巧玲课题组2026年第二批次博士研究生招生信息 +3 南风观火 2026-04-18 5/250 2026-04-20 10:13 by 南风观火
[考研] 通信工程求调剂！！！ +7 zlb770521 2026-04-14 7/350 2026-04-19 20:56 by Equinoxhua
[考研] 294求调剂 +8 淡然654321 2026-04-17 9/450 2026-04-19 19:51 by Equinoxhua
[考研] 291求调剂 +11 关忆北. 2026-04-14 11/550 2026-04-19 17:16 by 中豫男
[考研] 304求调剂 +8 castLight 2026-04-16 8/400 2026-04-19 17:14 by 中豫男
[考研] 求调剂 +10 小聂爱学习 2026-04-16 12/600 2026-04-19 16:51 by 中豫男
[考研] 求调剂 +6 苦命人。。。 2026-04-18 7/350 2026-04-19 16:27 by 中豫男
[考研] 307中医考研调剂 +9 于以采蘩 2026-04-14 9/450 2026-04-19 08:41 by 烟雨流涯
[考研] 294求调剂 +15 淡然654321 2026-04-15 15/750 2026-04-19 08:20 by cuisz
[考研] 300求调剂 +12 橙a777 2026-04-15 12/600 2026-04-18 23:51 by 路病情
[考研] 接受任何调剂 +6 也就是栗子 2026-04-17 7/350 2026-04-18 17:20 by 涵竹刘
[考研] 一志愿华中农业071010，320求调剂 +17 困困困困坤坤 2026-04-14 19/950 2026-04-17 20:08 by 关一盏灯cd
[有机交流] 二苯甲酮酸类衍生物 50+3 小白爱主人 2026-04-17 6/300 2026-04-17 18:47 by kf2781974
[考研] 295分求调剂 +5 ?要上岸? 2026-04-17 5/250 2026-04-17 16:51 by fenglj492
[考研] 药学求调剂 +14 喽哈加油 2026-04-14 16/800 2026-04-16 10:15 by beilsong20
信息提示
关闭
请填处理意见
关闭