Chinaunix

标题: 求满足1～100内任意数相减绝对值为素数个数 [打印本页]

作者: rookieljw 时间: 2012-10-24 20:47
标题: 求满足1～100内任意数相减绝对值为素数个数
如题，请问总得个数有多少？
小弟c还入门，就请用c编写吧！

作者: rookieljw 时间: 2012-10-24 20:49
补充下，应该说最多的个数

作者: Ager 时间: 2012-10-24 21:38
本帖最后由 Ager 于 2012-10-24 23:34 编辑

一行命令：
$ perl -e "map{my \$i=\$_;map{my \$j=abs(\$_-\$i);print qq~ABS(\$_-\$i)=~.\$j.qq~: PRIME\!\n~ if((1 x \$j)\!~/\^(11+)\1+\$/)&&(\$j\!~/\^[01]\$/)}(1..100);}(1..100);"

作者: mirnshi 时间: 2012-10-24 23:03
进来只是想说：作业题，还是要亲历亲为。

作者: starwing83 时间: 2012-10-25 03:49
本帖最后由 starwing83 于 2012-10-25 05:52 编辑

回复 3# Ager

你自己说，像不像乱码。

write-only语言，名不虚传啊

顺便说一下，我觉得python版本的似乎更短一点：

一行命令
$ python -c"r=range(1,101);print[(i, j)for i in r for j in r if abs(i-j)in[2]+[x for x in r if 2**x%x==2]]"

作者: jueshidouzi 时间: 2012-10-25 11:21
这是一个数学问题，我偶然也看到过。个人基本思路：
令 A = {x | x >= 1 && x <= 100}; B = {y | y >= 1 && y <= 100}
则 |x - y| = C = {z | z >= 0 && z <= 99};
那么求解问题的思路就出来了，即从2-99里找出所有的素数。（1既不是合数也不是素数）

作者: rookieljw 时间: 2012-10-25 17:30
回复 5# starwing83

py个人不懂，可是好像你看错题目了吧，问的是，满足任意两数相减为素数，求的是减数与被减数而不是值。
比如1~10，满足任意两数相减为素数的数最多为3个，分别为 1、4、6，（4-1=3,6-4=2,6-1=5）

作者: rookieljw 时间: 2012-10-25 17:31
回复 3# Ager

可是好像你看错题目了吧，问的是，满足任意两数相减为素数，求的是减数与被减数而不是值。
比如1~10，满足任意两数相减为素数的数最多为3个，分别为 1、4、6，（4-1=3,6-4=2,6-1=5）

作者: starwing83 时间: 2012-10-25 17:37
本帖最后由 starwing83 于 2012-10-25 17:38 编辑

回复 8# rookieljw

= =我照着那位写的……得到我们的结果，基本上在这个结果集合里面求一个最大等价集就可以了似乎……

作者: starwing83 时间: 2012-10-25 20:04
回复 8# rookieljw

我擦，被耍了！！！我写了三个多小时……

先开始出现一个很奇怪的现象，我写出来的程序求出的最大连通分量最大只有4。

我觉得很奇怪，就反着研究了一个倒推算法，还是只有4.

然后我开始觉得不对劲了，于是就证明了一下！！可以证明，如果有N个数字两两相减为素数，那么N最大不可能超过4！

可以这么想，假设N>=5，就设N为5好了，那么最小的五个数字分别为N1，N2，N3，N4，N5。我们假设他们单调上升，即最小的数字是N1，最大的是N5。

由定义可知，
P21 = N2 - N1
P32 = N3 - N2
P31 = N3 - N1

即相邻的三个数字相减绝对值必须为质数，这是题目规定。我们将这三个式子变形，很容易得：

P21 + P32 = P31

即，每三个数字之间，必定要有两个素数之和等于第三个素数。首先我们假设这三个素数中不存在2，那么显然这是不可能的：因为两个奇数相加为偶数，而素数中为偶数的只有2.

那么可知，在得到的序列里，每三个数字之间的两个差必定有一个是2。

现在我们说明在这种情况下，差素数的数量不可能大于3，假设数量大于3，则意味着：
P21 + P32 = P31
P21 + P32 + P43 = P41
P21 + P32 + P43 + P54 = P51

注意这三组式子，我们可以得知，P31一定是奇数，那么P43必定是2——否则P41一定是合数。也就是说：
P21 + P32 + P43 + P54 = P51
2 + P32 + 2 + P54 = P51
P32 + 4 + P54 = P51
注意！P32一定不是2，否则P31就是4不是素数。同理P54同样不可能是2，那么可知P32和P54都是奇数，那么P51就只可能是合数，由此可知，P51必定不存在。

即，满足要求的素数数量，最多只可能有3个，即，满足要求的数组集合，其最大大小只可能有4个！

我擦啊……你这不是耍人么？

作者: starwing83 时间: 2012-10-25 20:10
@rookieljw强烈要求补偿精神损失= =||||||

作者: starwing83 时间: 2012-10-25 20:12
得，一个伴晚搭进去了……吃饭去鸟……

作者: rookieljw 时间: 2012-10-26 09:22
回复 12# starwing83

不好意思，昨天上完体育很累，很早就睡了，太感谢你啦！大大。。

作者: rookieljw 时间: 2012-10-26 09:25
回复 10# starwing83

差素数为三，要求的数也是三吧

作者: starwing83 时间: 2012-10-26 12:55
回复 14# rookieljw

程序能得到4的结果，这里得到的是最多三个差素数，但是你别忘了还有一个和：
P1 + P2 + P3 = P4,

这个是很好理解的，我们已经证明了P1和P3肯定是2，那么只需要找相差为4的素数就可以了，相差为4最小的是3和7，那么设N1为1，则序列为：1,3,6,8，很容易证明他们任意两个数差的绝对值肯定为素数。那么问题转化为寻找100以内差为4的素数对……………………OK，明白了？

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)