计算机程序判断素数（一）

计算机程序如何判断一个数字是素数

素数定义：

“素数，也叫质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。”——来自百度百科

最朴素的想法：

将所有有可能的数都试一遍，即如果判断数字n是不是素数，将2到n-1都尝试一遍，只要不存在因数就说明数字n是素数。附python代码：

n = int(input())

for i in range(2, n):
    if n % i == 0:
        print('数字{}不是素数'.format(n))
        break
else:
    print('数字{}是素数'.format(n))

程序加速：

利用上述程序进行计算的时候，如果n很大，那程序会由于需要遍历的数太多而运行时间过长。此时就需要寻找程序加速的方法。

最简单的加速方法是减少遍历数的数量，研究表明只要遍历2到即可。附python代码

n = int(input())

for i in range(2, int(n**0.5)+1):
    if n % i == 0:
        print('数字{}不是素数'.format(n))
        break
else:
    print('数字{}是素数'.format(n))

其他加速方法：

在实际使用中，上述加速已经可以满足使用需求。

但是如果想要更快速度，还是有其他方法的：素数筛选法就是其中之一。

有兴趣可以找找其他大佬的博客，啥都有