BlueHacker查看:133 回复:5 评论:34 创建时间:2022-04-03T21:06:18用户:
# 开根（上舍）算法
def root(n):
n_root = int(n ** 0.5)+1
return n_root
# 定义必要变量
a = input('输入一个正整数n：')
a_prime_min = 0
a_prime_False = 0
# 防止报错
if a:
a = int(a)
# 核心算法
a_root = root(a)
for i in range(a_root-2):
j = int(i+2)
if a % j == 0:
a_prime_False = 1
a_prime_min = j
break
# 输出
if a_prime_False == 1:
print(a,'不是质数'),
print('它的最小质因子是：',a_prime_min)
print('\n\n')
else:
print(a,'是质数')
print('\n\n')
## author：BlueHacker code:5959102主要思路：
有一个大于2的正整数数n，对根号n及以下，2级以上的正整数集中任意一个数p，运算S=n%p，若存在p使得S = 0，则n是合数，否则n是质数。
证明：一个大于2的正整数n，若根号n及以下，2及以上的正整数都不能整除n，则n是质数.
设n是一个合数，n = pm，p是n的最小质因子，m是剩余部分.
m显然大于等于q.
下证：p <= 根号n.
假设 p > 根号n.
则p^2 > n.
因为 m >= q.
所以pm >= n.
因为 n = pm (题设).
矛盾！
所以p <= 根号n.
那么，如果没有p存在，则n不是合数，又n是大于等于2的正整数，所以n是质数.
命题成立.
证毕.
本算法结合数论，省去一大半计算量，使得计算速度加快至少60%
更好的理解方式：
数论补充：在某种意义上，合数n的因数在根号n左右边数量是对称的.
例子：16的因数：1,2,4,8,16.根号16是4，4左边有2个，右边也有两个.
那么，如果左边为0，则右边一定为0，看一下根号n是否为整数就行了
RTriangle显然不是最快
点赞0
评论
推 销 手 段
请问您知道有啥更快的算法吗？本人想学习下:)
一个是 素数一定满足除以6的余数为1或5 可以用这个先简单判断一下 还有一个 就是可以跳过一些没有必要的数 例如判断了不能被3整除，就可以直接跳过6,9,12等等 （其实应该是有更快的 但我看不懂了）
哦哦我知道，就是判断下面的素数，但是那样的话会麻烦一点，填个列表或者判断下面的数，但是。。。对于大数是差不多的
yee089费马小定理了解一下。
点赞0
评论
虽然不是很稳定，但是失手概率极低，而且是O(1)判断
用第2条？
有一种情况叫做费马骗子，所以要多做几次（）
但是p对模n的阶不一定是n-1啊
。。。。
费马小定理将成为费马质数检验的基础，这是一种确定一个数是否为质数的概率方法。例如，如果我们想知道n = 19是否为素数，随机取 1 < a < 19，假设a = 2。计算n−1 = 18，及其因子是9和6。我们通过计算2¹⁸ ≡ 1 （mod 19）， 2⁹ ≡ 18（mod 19）和 2⁶ ≡ 7 （mod 19）来检验，最后发现19必须是素数。（网上扒下来一段（））
如果要用费马小定理，应该从哪个角度去判断？
逆定理自然是不成立的
哈这个
我知道你什么意思了
找n-1的因数，然后看哪个因数是阶是吧
这个.....
很明显是不成立的哈
你看2
那个，n^p 同余 n（mod p ）不需要强调（n,p）=1，但是你那个n^（p-1）同余1（mod p ）是要强调（n，p）=1的，从推导过程中可以看出来。所以你那个东西有一定概率不成立
歪歪，出来解释下你的思路吧 :)
哈喽，在吗
溜了,哈哈 :)
BlueHacker【数论】本人再次普及费马小定理的三种表达方式，若您不感兴趣请跳过
点赞0
评论
第一种
条件：p是质数，(p,n)=1，n是正整数 --- 结论：n^(p-1) ≡ 1 (mod p)
-----------------------我是分界线------------------------------
第二种
条件：(p,n)=1，n是正整数 --> 结论：n^p ≡ n (mod p)
-----------------------我是分界线------------------------------
第三种
补充芝士：若p是质数，则必存在正整数m使得特定的一个n满足n^m ≡ 1 (mod p)，我们把所有正整数m组成数集A，若a是A中最小的，则称a是n对模p的阶。
（芝士被吃掉了）
条件：p是质数，n是正整数，数集A中含有所有正整数m使得特定的一个n满足n^m ≡ 1 (mod p)，a是n对模p的阶，k∈A --- 结论：a|k
-------上面是普及--------------我是分界线------------------下面是评论-------