判断一个数是否是质数

判断一个数是否是质数
最暴力的解法
利用质数的性质：设i为质数，则i只能被 1 和 i整除。
因此对于i，我们可以令 2..i-1 依次除以i，如果均不能被整除，则说明是质数。
代码如下
private static boolean isPrime1(int nr) {
for (int i = 2; i < nr; i++) {
if (nr % i == 0) return false;
}
return true;
}123456123456

稍微暴力的方法
同样利用其性质，但我们可以注意到，当 x > i / 2 时，则 x 肯定不能被 i 整除。
对于i，我们可以令 2..x 依次除以i，其中x为sqrt(i)
代码如下
private static boolean isPrime2(int nr) {
for (int i = 2; i*i <= nr; i++) {
if (nr % i == 0) return false;
}
return 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) 的质数合成）。
代码如下
private static void primeList(List 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);
}
} else {
return ;
}
}
}12345678910111234567891011

此算法存在的问题也很明显，说它是判断一个数是否是质数获取不太准确，其作用应该是 “打印出小于等于某值的所有质数”
使用素数表
上面的算法有一个缺陷，它对输入数组要求较高，要求包含了数组最大值之前的所有素数，且是已排序的。也就是说它不能用来直接判断一个数是否是素数。
通常情况下，我们会使用一个素数表。接着用来整除的元素便可以从这个素数表中获取
这种算法的局限在于素数表是有限的，对于超出素数表最大值平方的数则需要加上上述方法二的步骤才能判断（尽管这种情况不多）。
算法实现同上，只是此时直接从素数表获取素数即可
http://blog.csdn.net/lingeors/article/details/56288375?locationNum=13&fps=1

根据质数的定义，在判断一个数n是否是质数时，只要用1至n-1去除n，看看能否整除即可。
还有更好的办法：先找一个数m，使m的平方大于n，再用小于等于m的质数去除n（n为被除数），如果都不能整除，则n必然是质数。如我们要判断1993是不是质数，50*50>1993，那么只要用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，在100内共有25个质数。

只有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是合数。）

你新建一个Test类 把下面这些拷进去就是了哈

public class Test {

public static void main(String args[]) {
if(judgeNum(89)) System.out.println(89 + "是质数");
else {System.out.println(89 + "不是质数");}
}
/**
* 判断一个数是否是质数的方法
* @param num
* @return
*/
public static boolean judgeNum(long num) {
boolean flag = true;
if(num < 2) return false;//小于2肯定不是
for(int i = 2; i <= num / 2; i++) {//从2开始循环到他的一半
if(num % i == 0) flag = false;//如果有能被他整除的 那么他不是
}
return flag;//没有就是了
}
}

除了1和这个数本身相乘能得这个数以外，没有其他两个整数相乘能等于这个数
比如2，只能写成1乘2，就是质数
像4，能分成 1乘4 和 2乘2 ，这种就不是质数

素数就是质数 就是除了1和它本身以外不能被任何数整除的数 比如 2,3,5,7,11等等