「python」寻找素数

之前自学过python,写过自动化脚本，也自学过django项目开发，但纯属囫囵吞枣式的，拜读该项目之后，还是想系统性的学习一下，此文就算作开篇。
此文是对应的项目第四章节，示例代码涉及到一些算法题，边刷题边学语言了，这里记录一下

1 输入一个数判断是不是素数

【素数】质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；0和1既不是质数也不是合数，最小的质数是2

代码示例

如果不看代码，要我写，我可能还真的完全最直白的方式，当然也是最低效率的写法：

# _*_ coding: utf-8 _*_
__author__ = 'ing'
__date__ = '2019-07-15 14:48'


num = int(input('请输入一个正整数:'))
is_prime = True
for i in range(2, num):
    if num % i == 0:
        is_prime = True
        break

if is_prime and num != 1:
    print('%d是素数' % num)
else:
    print('%d不是素数' % num)

项目里的写法高效一点

# _*_ coding: utf-8 _*_
__author__ = 'ing'
__date__ = '2019-07-15 14:48'

"""输入一个正整数判断它不是素数"""

from math import sqrt

num = int(input('请输入一个正整数:'))
end = int(sqrt(num))
is_prime = True
for x in range(2, end + 1):
    if num % x == 0:
        is_prime = False
        break
if is_prime and num != 1:
    print('%d是素数' % num)
else:
    print('%d不是素数' % num)

是通过开平方根的方式判断的，至于原因：
因为如果它不是素数（也就是合数），那么它一定可以表示成两个数（除了1和它本身）相乘，这两个数必然有一个小于等于它的平方根，只要找到小于或等于的，也就证明他不是素数了。

这里拓展下知识，其实还有一个更高效的方法可以叫做6倍原理：

就是说素数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

如何论证，首先 6x 肯定不是素数，因为它能被 6 整除；其次 6x+2 肯定也不是素数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是素数了。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可

# _*_ coding: utf-8 _*_
__author__ = 'ing'
__date__ = '2019-07-15 18:05'

"""输入一个正整数判断它不是素数"""

from math import sqrt

num = int(input('请输入一个正整数:'))
end = int(sqrt(num))

is_prime = True

if num % 6 != 1 and num % 6 != 5:
    is_prime = False

for i in range(5, end + 1, 6):
    if num % i == 0 or num % (i + 2) == 0:
        is_prime = False
        break

if is_prime and num != 1:
    print('%d是素数' % num)
else:
    print('%d不是素数' % num)

另外还有一个示例是穷举法计算两个正整数的最大公约数和最小公倍数

# _*_ coding: utf-8 _*_
__author__ = 'ing'
__date__ = '2019-07-15 14:56'
"""计算两个正整数的最大公约数和最小公倍数
"""

x = int(input('x= '))
y = int(input('y= '))

if x > y:
    x, y = y, x

for factor in range(x, 0, -1):
    if x % factor == 0 and y % factor == 0:
        print('%d和%d的最大公约数是%d' % (x, y, factor))
        print('%d和%d的最小公倍数是%d' % (x, y, x * y // factor))
        break