数学中国

标题: [悬赏] 素数判别猜想 [打印本页]
作者: 王守恩    时间: 2021-8-21 10:58
标题: [悬赏] 素数判别猜想
本帖最后由 王守恩 于 2021-8-21 18:31 编辑

各位网友，您能举出反例来？谢谢！

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

\(\lceil |[\frac{(n+\lceil n/2\rceil )!}{n*n!\ \lceil n/2\rceil !}]-\frac{\ 1\ }{n}|\rceil\) =0，则：n 为素数。

\(\lceil |[\frac{(n+\lceil n/2\rceil )!}{n*n!\ \lceil n/2\rceil !}]-\frac{\ 1\ }{n}|\rceil\) =1，则：n 为合数。

\(\lceil\ \ \rceil\) 表示小数部分作 1，\(|\ \ |\) 表示取绝对值，[  ] 表示取小数部分

0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1,
0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0,
1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0,
1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1,
0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, ...}
作者: awei    时间: 2021-8-21 12:21
这些符号都是以前定义过的，您定义的看着有点难受
\(\lfloor x\rfloor\)，向下取整符号。如：\(\lfloor 3.14\rfloor\)=3，\(\lfloor -3.14\rfloor\)=-4
\(\lceil x\rceil\)，向上取整符号。如：\(\lceil 3.14\rceil\)=4，\(\lceil -3.14\rceil\)=-2
[x],取整数部分符号。如：[3.14]=3，[-3.14]=-3
{x}取小数部分符号。如：{3.14}=0.14，{-3.14}=-0.14
始终要有x=[x]+{x}，这几个取整符号的用法是不一样的
作者: 王守恩    时间: 2021-8-21 12:24
本帖最后由 王守恩 于 2021-8-21 12:36 编辑
awei 发表于 2021-8-21 12:21
这些符号都是以前定义过的，您定义的看着有点难受
\(\lfloor x\rfloor\)，向下取整符号。如：\(\lfloor 3. ...


各位网友，您能举出反例来？谢谢！

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

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

\(\lceil |\){\(\frac{(n+\lceil n/2\rceil )!}{n*n!\ \lceil n/2\rceil !}\)}\(-\frac{\ 1\ }{n}|\rceil\) =1，则：n 为合数。



0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1,
0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0,
1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0,
1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1,
0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, ...}
作者: awei    时间: 2021-8-21 12:34
威尔逊定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
那么简单不用，为什么要搞那么复杂呢，最终还是用威尔逊定理来分析
作者: 王守恩    时间: 2021-8-21 16:20
本帖最后由 王守恩 于 2021-8-21 16:23 编辑
awei 发表于 2021-8-21 12:34
威尔逊定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
那么简单不用，为什么要搞那么复杂呢，最终还 ...


太丑了，改一下。

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

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

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



作者: 王守恩    时间: 2021-8-21 21:20
本帖最后由 王守恩 于 2021-8-21 21:29 编辑
awei 发表于 2021-8-21 12:34
威尔逊定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
那么简单不用，为什么要搞那么复杂呢，最终还 ...


这样也行。

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

{\(\frac{(3k+2)!/(2k+1)}{(k+1)!\ (2k+1)!}\)}*(2k+1)=1，则：(2k+1) 为素数。

  {  } 表示取小数部分,

{1, 1, 1, 4, 1, 1, 9, 1, 1, 18, 1, 21, 13, 1, 1, 15, 0, 1, 30, 1, 1, 30, 1, 22, 21, 1, 43, 42, 1, 1, 57, 47, 1, 27,
1, 1, 69, 21, 1, 13, 1, 55, 33, 1, 42, 66, 40, 1, 66, 1, 1, 45, 1, 1, 78, 1, 90, 78, 103, 12, 45, 121, 1, 90, 1,
63, 120, 1, 1, 51, 39,50, 60, 1, 1, 18,114, 1, 57,74, 1, 66, 1, 92, 12, 1, 70,63, 1, 1, 126,95, 33, 21, 1,  1,
75, 1, 1, 138, 120,185,117, 55, 1, 75, 150, 151,150, 170,1, 90, 1, 1, 0, 1, 115,162, 1, 1, 13,70, 0, 87, 1,
113, 153, 1, 231, 48, 1, 127,93, 1, 1, 0, 78, 1, 33, 1, 1, 0, 161,137,198, 1, 80,228, 130,77, 105,204, 1,..}
作者: awei    时间: 2021-8-21 21:35
本帖最后由 awei 于 2021-8-21 21:37 编辑
王守恩 发表于 2021-8-21 21:20
这样也行。

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


为什么威尔逊定理没有应用到实际的素数检测中去，
阶乘的运算量太大了，算法的时间复杂度太高了，实际素数检测中用不到，只能停留在分析层面上。
素数检测是为了把难题变简单，而不是变成更难的问题，
只要看到阶乘检测素数的，基本可以说是无用的，要不您换个大一点的数，\(2^{100}-1\)怎么样
作者: awei    时间: 2021-8-22 03:03
本帖最后由 awei 于 2021-8-22 03:07 编辑
王守恩 发表于 2021-8-21 21:20
这样也行。

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


如果成立的话，也可以这样表述，2k+1当且仅当为质数时，
\[C_{3k + 2}^{2k + 1} \equiv 1{\rm{\quad mod }}\left( {2k + 1} \right)\]
作者: 王守恩    时间: 2021-8-22 08:48
本帖最后由 王守恩 于 2021-8-22 10:16 编辑
awei 发表于 2021-8-21 12:34
威尔逊定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
那么简单不用，为什么要搞那么复杂呢，最终还 ...


威尔逊定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
那么简单不用，为什么要搞那么复杂呢，最终还是用威尔逊定理来分析。
说得好：取小数部分与取 mod 是同一回事。数学还是蛮好玩的。

主帖(1楼)可以化简。

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

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

\(\lceil\){\(\frac{n!+1}{n+1}\)}\(\rceil\)=1，则：n+1 为合数。

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

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

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

威尔逊定理理解起来也蛮好记的
如果设a和a拔是对于模p的乘法逆元，
那么只有1和-1的乘法逆元是自身，其余两两成对，
所以(p-1)!+1≡0  mod(p),您别理解错了
[attach]100073[/attach]
作者: awei    时间: 2021-8-22 11:09
本帖最后由 awei 于 2021-8-22 11:10 编辑
王守恩 发表于 2021-8-22 08:48
威尔逊定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
那么简单不用，为什么要搞那么复杂呢，最 ...


这次改对了，符号太多了
作者: awei    时间: 2021-8-22 11:19
本帖最后由 awei 于 2021-8-22 11:22 编辑

如果想用一个数字来描述素数的分布规律，
\(\sum_{n＝1}^{∞}2^{-p_n}\)这个常数应该是最准确最简洁的
有兴趣玩玩看看，这个已经被OEIS收录了。
作者: awei    时间: 2021-8-22 15:14
OEIS编码A051006
0.41468250985111166024810962215430770836577423813792……
\(P_n\)表示第n个数。
[attach]100143[/attach]
作者: 王守恩    时间: 2021-8-23 10:18
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 13:49
本帖最后由 awei 于 2021-8-23 14:02 编辑
王守恩 发表于 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.
只能有两种结果，似乎好些数都遵循这个规律，
威尔逊定理不过是个特例罢了，但不知道为什么



作者: 王守恩    时间: 2021-8-23 19:04
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-24 06:33
本帖最后由 王守恩 于 2021-8-24 06:38 编辑
王守恩 发表于 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,...
作者: 王守恩    时间: 2021-8-24 08:45
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 09:39
本帖最后由 chaoshikong 于 2021-8-24 09:41 编辑
王守恩 发表于 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的阶乘少很多，除非有更快的计算阶乘的方法，可以减少循环次数。。。
作者: 王守恩    时间: 2021-8-26 07:26
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} 最小公倍数。
作者: 王守恩    时间: 2021-8-27 08:30
本帖最后由 王守恩 于 2021-8-27 10:28 编辑
王守恩 发表于 2021-8-26 07:26
这样简单些(每个数只要计算1次，就可以判定)。

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

这样就行：任意 1 个数,只要计算 1 次，就可以判定(不用筛分，不用循环)。

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

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

\(\sqrt{n}\ !\ 不就是一个具体的数吗？\)
作者: 王守恩    时间: 2021-9-1 11:03
本帖最后由 王守恩 于 2021-9-1 11:05 编辑
chaoshikong 发表于 2021-8-24 09:39
感觉计算量并没有减少啊。。。

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

但用程序判定某数是否为素数，还有更好的办法，
就是素数终始出现在6n-1和6n+1上，所以循环次数大大减少，如：
5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67,
71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125,
127, 131, 133, 137, 139, 143, 145, \149, 151, 155, 157, 161, 163, 167, 169, .............

\(a(n)=\cos(n\pi)+6\lceil\frac{n}{2}\rceil\)



欢迎光临 数学中国 (http://www.mathchina.com/bbs/) Powered by Discuz! X3.4