【趣味学算法】13_素数

注： 本系列仅为个人学习笔记，学习内容为《算法小讲堂》（视频传送门），通俗易懂适合编程入门小白，需要具备python语言基础，本人小白，如内容有误感谢您的批评指正

素数就是只能被1和它自身整除的整数。

那么要判断一个整数a是否为素数就是要判断整数a能否被除1和它自身以外的任何整数所整除，如果不能整除则a为素数。

这里再介绍一个合数的概念，合数$m$可以拆成两个因数相乘，这两个因数一定一个小于等于$\sqrt{m}$，一个大于等于$\sqrt{m}$，就拿$16$举例

$1\times 162\times 84\times 48\times 216\times 1$

根据以上列出的因数组合可以看出在4的平方之后的因数跟之前是对称的，所以我们只需要判断在$\sqrt{m}$之前是否存在一个能整除$m$的数即可

那么接下来用代码实现求自定义输入范围内的素数

print("请输入一个整数范围(起start-终end): ")
start = int(input("start = "))
end = int(input("end = "))
while not (start > 0 and start < end):
    print("输入的参数有误！快给我重新输入：")
    start = int(input("start ="))
    end = int(input("end = "))
    
print('{}--{}之间的素数为：'.format(start,end))
for n in range(start,end):
    flag = 1
    i=2
    while i<=math.sqrt(n):
        if n%i== 0:
            flag=0
            break
        i += 1
    if flag == 1:
        print(n)

输出结果

请输入一个整数范围(起start-终end): 
start = 6
end = 1
输入的参数有误！快给我重新输入：
start =2
end = 9
2--9之间的素数为：
2
3
5
7

结合前面所学的内容，找到10000以内的回文素数，也就是既是回文数又是素数的数，代码实现如下:

def prime(num):
    i=2
    while i<=math.sqrt(num):
        if num%i== 0:
            return 0
        i += 1
    return 1

m =int(input('请输入一个整数：'))
print('{}以内的回文素数为：'.format(m))
for num in range(m):
    k = len(str(num))-1
    i = 0
    S = 0
    while i <= k:
        S += (num//10**i%10)*10**(k-i)
        i += 1
    if num>10 and S==num and prime(num):
        print(num)

输出结果：

请输入一个整数：10000
10000以内的回文素数为：
11
101
131
151
181
191
313
353
373
383
727
757
787
797
919
929