求满足1～100内任意数相减绝对值为素数个数

rookieljw

如题，请问总得个数有多少？
小弟c还入门，就请用c编写吧！

rookieljw

补充下，应该说最多的个数

Ager

一行命令： $ 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

进来只是想说：作业题，还是要亲历亲为。

starwing83

回复 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

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

rookieljw

回复 5# starwing83


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

rookieljw

回复 3# Ager


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

starwing83

回复 8# rookieljw


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

starwing83

回复 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个！

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