[悬赏] 素数判别猜想

awei

王守恩 发表于 2021-8-22 08:48
威尔逊定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
那么简单不用，为什么要搞那么复杂呢，最 ...

这次改对了，符号太多了

awei

如果想用一个数字来描述素数的分布规律，
\(\sum_{n＝1}^{∞}2^{-p_n}\)这个常数应该是最准确最简洁的
有兴趣玩玩看看，这个已经被OEIS收录了。

awei

OEIS编码A051006
0.41468250985111166024810962215430770836577423813792……
\(P_n\)表示第n个数。

王守恩

awei 发表于 2021-8-22 11:09
这次改对了，符号太多了

这样更直观。把 0 删除，就是《素数表》。

n=5, 6, 7, 8, 9, ....    \(n^2\){\(\frac{(n-2)!}{n}\)}

{5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 0, 0, 23, 0, 0, 0, 0, 0, 29, 0, 31, 0, 0, 0, 0, 0,37, 0,
0, 0, 41, 0, 43, 0, 0, 0, 47, 0, 0, 0, 0, 0,  53, 0, 0, 0, 0, 0, 59, 0, 61, 0, 0, 0, 0, 0, 67, 0, 0, 0, 71, 0,
73, 0, 0, 0, 0, 0, 79, 0, 0, 0, 83, 0, 0, 0, 0, 0, 89, 0, 0, 0, 0, 0, 0, 0, 97, 0, 0, 0, 101, 0, 103, 0, 0, 0,
0,107, 0, 109, 0, 0, 0, 113, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 127, 0, 0, 0, 131, 0, 0, 0, 0, 0,137, 0,
139, 0, 0, 0, 0, 0, 0, 0, 0, 0, 149, 0, 151,  0, 0, 0, 0, 0, 157, 0, 0, 0, 0, 0, 163, 0, 0, 0, 167,  0, 0, 0,
0,173, 0, 0, 0, 0, 0, 179, 0, 181,0,0,0, 0, 0, 0, 0, 0, 0, 191, 0, 193, 0, 0, 0, 197, 0,197, 0, 199, 0,....

  参考 A000040：通项公式与这里不同。

awei

王守恩 发表于 2021-8-23 10:18
这样更直观。把 0 删除，就是《素数表》。

n=5, 6, 7, 8, 9, ....    \(n^2\){\(\frac{(n-2)!}{n}\)}
...

这还是威尔逊定理的变形呢，
那个定理严格证明起来还是有些绕，自己百度吧
其实我也有奇怪的发现
a_k和n互质，φ(n)表欧拉函数值
\[\begin{array}{l}
(a\_k,n) = 1\\
\{ a\_k\}  = \{ 1,2,3, \cdots  \cdots ,n - 1\}
\end{array}\]
\[\left\{ \begin{array}{l}
\prod\limits_{k = 1}^{\varphi \left( n \right)} {a\_k}  \equiv 1\bmod (n)\\
\prod\limits_{n = 1}^{\varphi \left( n \right)} {a\_k}  \equiv  - 1\bmod (n)
\end{array} \right.\]
把所有小于n并且与n互质的正整数相乘，除以n的余数不是1就是n-1.
只能有两种结果，似乎好些数都遵循这个规律，
威尔逊定理不过是个特例罢了，但不知道为什么

王守恩

awei 发表于 2021-8-23 13:49
这还是威尔逊定理的变形呢，
那个定理严格证明起来还是有些绕，自己百度吧
其实我也有奇怪的发现

谢谢网友 awei ！受 15 楼启发，对计算量作裁减。

n=10, 11, 12, 13, 14, 15, 16,17, .......

\(\lceil\){\(\frac{\lceil n/2\rceil!}{n}\)}\(\rceil\)=1，则：n 为素数。

0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0,...}

王守恩

王守恩 发表于 2021-8-23 10:18
这样更直观。把 0 删除，就是《素数表》。

n=5, 6, 7, 8, 9, ....    \(n^2\){\(\frac{(n-2)!}{n}\)}
...

接 14 楼。把 0 删除，就是《素数表》。谢谢网友 awei ！

n=10, 11, 12, 13, 14, 15, .......   \(n\lceil\){\(\frac{\lceil n/2\rceil!}{n}\)}\(\rceil\)

0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 0, 0, 23, 0, 0, 0, 0, 0, 29, 0, 31, 0, 0, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0,
0, 0, 47, 0, 0, 0, 0, 0, 53, 0, 0, 0, 0, 0, 59, 0, 61, 0, 0, 0, 0, 0, 67, 0, 0, 0, 71, 0, 73, 0, 0, 0, 0, 0, 79, 0,
0, 0, 83, 0, 0, 0, 0, 0, 89, 0, 0, 0, 0, 0, 0, 0,  97, 0, 0, 0, 101, 0, 103, 0, 0, 0, 107, 0,  109, 0, 0, 0, 113,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,127, 0, 0, 0,131, 0, 0, 0, 0, 0, 137, 0, 139, 0, 0, 0, 0, 0, 0, 0, 0, 0,149,
0, 151, 0, 0, 0, 0, 0,157, 0, 0, 0, 0, 0, 163, 0, 0, 0,167, 0, 0, 0, 0, 0, 173, 0, 0, 0, 0, 0,179, 0, 181, 0, 0,
0, 0, 0, 0, 0, 0, 0,191, 0, 193, 0, 0, 0, 197, 0,199, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 211, 0, 0, 0, 0, 0, 0, 0,...

王守恩

awei 发表于 2021-8-21 21:35
为什么威尔逊定理没有应用到实际的素数检测中去，
阶乘的运算量太大了，算法的时间复杂度太高了，实际 ...

不用"!"也可以。

n=2, 3, 4, 5, 6, 7, .......

\(\lfloor\frac{n}{Product(k, (k, Divisors(n)))}\rfloor\)=1，则：n 为素数。

1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0,
1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,...}

chaoshikong

王守恩 发表于 2021-8-24 06:33
接 14 楼。把 0 删除，就是《素数表》。谢谢网友 awei ！

n=10, 11, 12, 13, 14, 15, .......   \(n ...

感觉计算量并没有减少啊。。。

比如我写个程序识别n是否为素数，我也只需要把n分别除以2到\(\sqrt n\)，每个都不能整除则为素数。
程序代码为：

1. bool isPrime_1( int num )
   
2. {
   
3.      int tmp =sqrt( num);
   
4.      for(int i= 2;i <=tmp; i++)
   
5.         if(num %i== 0)
   
6.           return 0 ;
   
7.      return 1 ;
   
8. }

复制代码

而现在是(n/2)!，也就是要乘以2到n/2次，上面的方法是要除以2到\(\sqrt n\)次，循环次数还少一些，只不过要多做判定次数，所以速度慢不了多少

但用程序判定某数是否为素数，还有更好的办法，就是素数终始出现在6n-1和6n+1上，所以循环次数大大减少，如：

1. bool isPrime_2( int num )
   
2. {
   
3.                  //两个较小数另外处理
   
4.                  if(num ==2|| num==3 )
   
5.                                  return 1 ;
   
6.                  //不在6的倍数两侧的一定不是质数
   
7.                  if(num %6!= 1&&num %6!= 5)
   
8.                                  return 0 ;
   
9.                  int tmp =sqrt( num);
   
10.                  //在6的倍数两侧的也可能不是质数
    
11.                  for(int i= 5;i <=tmp; i+=6 )
    
12.                                  if(num %i== 0 || num %(i+ 2)==0 )
    
13.                                                  return 0 ;
    
14.                  //排除所有，剩余的是质数
    
15.                  return 1 ;
    
16. }
    

复制代码

那这个程序的判定方法循环次数更少，比计算n/2的阶乘少很多，除非有更快的计算阶乘的方法，可以减少循环次数。。。

王守恩

chaoshikong 发表于 2021-8-24 09:39
感觉计算量并没有减少啊。。。

比如我写个程序识别n是否为素数，我也只需要把n分别除以2到\(\sqrt n ...

这样简单些(每个数只要计算1次，就可以判定)。

n=1, 2, 3, 4, 5, 6, 7, .......

{\(\frac{\sqrt{n}\ !}{n}\)}\(=\frac{b}{a}\)(既约分数)，当 a=n 时，n 为素数。

{\(\frac{LCM(n)}{n}\)}\(=\frac{b}{a}\)(既约分数)，当 a=n 时，n 为素数。

\(LCM(n)\) 表示 {1, 2, 3, ...., n} 最小公倍数。