怎么判断一个数是不是质数

关于怎么判断一个数是不是质数的知识点，泰山头条网将为你整理了下面这些知识。

怎么判断一个数是不是质数

一个大于1的整数，如果只能被1和他本身整除，就称为质数。对于小的数我们可以通过分解质因数来判断它是不是质数。但是对于大的数，分解就不那么容易了。那么我们可以利用一些数学知识来判断一个大的数是不是质数。

试除法是一种最朴素的判断质数的方法。把整数N分别除以2到sqrt(N)中所有的数，如果都除不尽，就是质数。

例子: 我们要判断121是不是质数。 sqrt(121)等于11，因此我们只需要把121除以2到11中的数即可。我们发现，121是11乘以11，所以它是合数。

当然，试除法很好用，但是它并不适用于大的数。试除法有很明显的缺点，就是对待于很大的开始我们需要枚举这么多的数，这个非常浪费计算资源。因此，在很多情况下，我们需要利用更高级的算法来进行质数筛选。

欧拉筛法是一种比较简单的质数筛选方法，它利用了欧拉筛法所具有的时间效率很高这个特点，可以在极短的时间内计算出亿级别的数的结果。它是线性筛选质数的一种优化，时间复杂度为O(n)。

欧拉筛法思路:

我们仍然考虑试除法，但我们注意到每个合数都会被他的最小质因子筛掉。而曾经被他的一个质因子筛掉的数，必定被他的另外一个质因子筛掉。例如：6 由于2的筛减而被筛去了，那么三不可能再将其筛去，因为6已经与2缺少互质的条件了。

算法模型: 1. 先将所有小于N的质数筛出来 2. 对于待判定的N, 一步一步试除小于sqrt(N)的所有质数，直到发现一个能整除它。 3. 如果没有发现合适的质因子，那么N就是一个质数。

例子: 我们仍然拿121来说。我们的程序先筛选出小于sqrt(121)的质数，那么[2,3,5,7,11]这几个数. 然后我们按照它们的倍数从N中删除，当然，只有在符合i % primes[j]==0的时候才进行删除。

现在我们已经知道了两种方法判断一个数是不是质数了。试除法简单易用，欧拉筛法更加高效。当然，实际情况会比我们的算法复杂得多，就像RSA算法一样，众所周知，它可以解出来所有的小素数和一些大素数。因此，发展高效的筛选质数算法，已经成为了计算机领域最为关注的问题之一。