24小时热门版块排行榜    

查看: 1287  |  回复: 15
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

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 ]
回复此楼
已阅   回复此楼   关注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 ]
漩涡的中心有一块空地,空空的。
3楼2011-06-16 11:50:23
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)


小木虫(金币+0.5):给个红包,谢谢回帖
引用回帖:
Originally posted by sudo at 2011-06-16 10:43:17:
“产生最多的质数”这个说法有点模糊呢,看例子,是不是指n从0开始取,然后递增1,直到式子n^2 + an + b不再为质数为止,这个过程中n的个数呢?

然后那个80个质数的例子是暗示一个上限吗

80^2 + 1000*8 ...

很高的洞察力哈~佩服佩服~
阁下莫非是根据1601超过1000判断这个上限的?
漩涡的中心有一块空地,空空的。
6楼2011-06-16 16:49:20
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)


小木虫(金币+0.5):给个红包,谢谢回帖
引用回帖:
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++)
        {
...

问下,代码里面的测试数据为啥能限制在80个以内?这个上限怎么确定的呃?
漩涡的中心有一块空地,空空的。
11楼2011-06-16 18:26:38
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)

★ ★ ★
小木虫(金币+0.5):给个红包,谢谢回帖
余泽成(金币+2): 鼓励讨论! 2011-06-18 16:10:05
引用回帖:
Originally posted by sudo at 2011-06-16 18:39:03:
其实无上限也无所谓..反正有break..

当然他那么写,也是觉得2楼我说的那个“暗示”是存在的...事实证明应该也是存在的吧...哈哈哈...

看,经历过中国的考试,“出题人意图”这种事情就能看透

哎,我就感觉错了呀,看来我还是缺乏考试的磨练。
我收到的暗示是a要么正数要么负数,负数产生的应该会多一些。理由嘛,对称轴。
漩涡的中心有一块空地,空空的。
15楼2011-06-16 19:01:19
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)


小木虫(金币+0.5):给个红包,谢谢回帖
引用回帖:
Originally posted by libralibra at 2011-06-16 18:46:06:
我就是根据提示的第二个牛式子观察的,80的时候,abs(b)大于1000了,所以应该结果要小于80个

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

牛子式,这名字起的好~
漩涡的中心有一块空地,空空的。
16楼2011-06-16 19:06:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
普通表情 高级回复(可上传附件)
信息提示
请填处理意见