猫史档案馆

# 开根（上舍）算法
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是否为整数就行了