判断一个数是否是质数的两种方法

判断一个数是不是质数（判断一个数是不是质数的程序）

在本文中，科普知识网将告诉你判断一个数是否为质数的知识点，以及判断一个数是否为质数所对应的程序。如果对你有帮助，请别忘了收藏本站！

本文简介:

1.如何快速判断一个数是质数还是复数？

2.确定一个数是否是质数。

3.如何判断一个数是质数还是复数？

4.如何判断一个数是不是质数？以51为例来说明。

5.如何判断一个数是不是质数？

6.如何判断一个数是不是质数？

如何快速判别一个数是质数还是合数

简单来说，有两种方式。

1.用试除法判断一个自然数A是不是质数时，从小到大依次去掉每个质数中的A。如果一个质数是整除的，这个A可以判断为不是质数；如果不能整除，当不完全商小于这个素数时，就没有必要继续试除了。可以得出结论，A一定是素数。

2.只要x是奇数，平方差是偶数(这是确定的)，a2-b2=(a+b)(a-b)就是两个因子。

比如26341，先找一个比26341大的偶数平方数，26896，和它的差是555，肯定不是平方数，然后下一个平方数(其实考虑到(x+1) 2 = x2+2x+1，直接把2x+1加到原数上就够了，不需要计算x+1的平方)，，，，，，，，，，，下一个2559也不是(一眼就能看出来是下一个差是3，然后下一个，再下一个...找出规律很快，最后221 ^ 2 = 48841，48841-26341 = 22500，显然是22500 = 150 ^ 2。

判断一个数是否是质数。

最暴力的解决方案

利用素数的性质:设我是素数，那么我只能被1和I整除。

因此，对于I，我们可以除以2..i-1依次由I。如果没有一个能被整除，说明是质数。

代码如下所示

私有静态布尔isPrime1(int nr) {

for(int I = 2；i nri++) {

if (nr % i == 0)返回false

}

返回true

}123456123456

有点暴力的方法

利用同样的性质，我们可以注意到，当x为i/2时，那么x肯定不能被I整除。

对于I，我们可以除以2..x依次乘以I，其中x是sqrt(i)

代码如下所示

私有静态布尔isPrime2(int nr) {

for(int I = 2；i * i = nri++) {

if (nr % i == 0)返回false

}

返回true

}123456123456

更有效的算法

提供一个数组nums = {2，3，4，5，...17}

我们知道nums[0]是素数，去掉nums中所有能被nums[0]整除的数。此时数组为nus = {2，3，5，7，9，11，13，15，17}

然后去掉所有能被3整除的数。此时，nums = {2，3，5，7，11，13，17}

下一个数字是5，因为5*5是17，所以删除过程结束。此时，的nums值是输入nums中的所有素数。

以上步骤之所以正确，是因为素数相乘可以得到一个合数。对于任意一个素数I，如果它不能被sqrt(i)之前的所有素数整除，那么它一定是一个素数(小于sqrt(i)的合数可以由小于sqrt(i)的素数合成)。

代码如下所示

私有静态空素数列表(ListInteger nums) {

for(int I = 0；I nums . size()；i++) {

if(nums . get(I)* nums . get(I)= nums . get(nums . size()-1)){

for(int j = I+1；j nums . size()；j++) {

if(nums . get(j)% nums . get(I)= = 0)nums . remove(j)；

}

}否则{

返回；

}

}

}12345678910111234567891011

这个算法的问题也很明显。判断一个数是不是质数是不准确的，它的作用应该是“打印出所有小于等于某个值的质数”

使用质数表

上面的算法有一个缺陷。它要求输入数组包含数组最大值之前的所有素数，并且是有序的。也就是说不能用来直接判断一个数是不是素数。

通常，我们会使用素数表。可整除的元素可以从这个素数表中得到。

这种算法的局限性在于素数表是有限的，超过素数表最大值平方的数需要加上上述方法2的步骤来判断(虽然这种情况很少)。

算法同上，但此时可以直接从素数表中获取素数。

http://blog.csdn.net/lingeors/article/details/56288375?位置数量=13fps=1

如何判断一个数是质数还是复数，那么:

1.当这个数大于7时:分别除以2、3、5和7。如果这个数不能被2、3、5、7整除，那么这个数就是质数。只要这个数能除以2、3、5、7中的任意数，那么这个数就是合数。

2:当这个数小于等于7时，你只需要记住2，3，5，7是质数就可以了。

如何判断一个数是不是质数？以51为例说明一个数是不是质数，主要看这个数有多少个因子。如果除了1和它本身还有其他因子，则是合数，如果只有1和它本身两个因子，则是质数。比如51除了1，51和3，17还有两个因子，所以51是合数，不是质数。

如何判断一个数是不是质数？一个质数可以被1和它本身整除，但是其他的都不能被整除。

比如3，3只能被1和3整除，其他的不能。质数是指在所有大于1的整数中，除了1和它本身，没有其他除数。这种整数叫质数或素数。也可以说，素数只有1和它自己的两个约数。

素数的概念，称为质数或素数，是一个除了自身和1之外没有其他因素的正整数。比如2，3，5，7是质数，4，6，8，9不是。后者称为合数。从这个角度来说，整数可以分为两种，一种叫质数，一种叫合数。(有人认为数字1不应该被称为质数。)著名的高斯“唯一分解定理”说，任何整数。可以写成一系列素数的乘积。

如何判断一个数是不是质数？根据质数的定义，判断一个数n是否质数时，只需将n除以1到n-1，看它是否能被整除。

有更好的办法:先找一个数m，使m的平方大于n，然后用一个小于等于m的质数除以n(n为被除数)。如果两者都不可分，那么n一定是质数。如果要判断1993是不是质数，50*501993，那么只要把1993除以50这个质数，看能不能整除，否则就是质数。100以内有25个质数，很好记。只要把100以内的质数背下来，就能很快判断出10000以内的数是不是质数。

100以内的质数是2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97。

只有1和它自己的两个因子的自然数叫做素数(或称质数)。(比如从2÷1=2，2÷2=1可以知道，2的因子只有两个约数:1和2本身，所以2是素数。相反的是合数:“除了1和它本身的两个因子，还有其他的因子，叫合数。”比如4÷1=4，4÷2=2，4÷4=1。显然，4的因子除了1和它本身的4之外，还有一个因子2，所以4是一个合数。)

判断一个数是否质数的介绍和判断一个数是否质数的程序到此结束。不知道你有没有找到你需要的资料？如果你想了解更多这方面的内容，记得收藏并关注这个网站。