Java质数算法介绍

Java质数算法是什么？极悦小编来为大家解答。质数就是一个数只可以被它自己和1整除(1不是质数)

1.判断一个数是不是质数

只需要让这个数循环除以2到根号n的数 如果出现整除的现象，则不是质数，反之则为质数

源代码：

	public static int F(int x) {   //判断是否为质数 2，3，5，7，11，13，17，19......
		if(x==1) return 0;
		for(int i=2;i<=x/i;i++)
		{
			System.out.println(x+ " "+ i);
			if(x%i==0)
				return 0;
		}
		return 1;
	}

除了判断是否是质数，我们还可以分解质因数

2.分解质因数

根据算术基本定理又称唯一分解定理，对于任何一个合数， 我们都可以用几个质数的幂的乘积来表示。

算法逻辑描述：循环找质因数，找到时循环继续除以这个数，记录个数，直到不整除时退出循环继续找下一个质因数，如果最后n不是1，说明还有最后一个质因数也就是它本身n，输出出来。

源代码：

	public static void prime(int n){
	    for(int i = 2; i <= n / i; i++){      循环到根号n为止
	        int a = 0, b = 0;
	        while(n % i == 0){                如果可以整除说明是质因数
	            a = i;
	            n /= i;                       一直除以这个数直到不整除为止
	            b++;                          累计a的个数
	        }
	        if(b > 0)
	            System.out.println(a + " " + b);
	    }
	    if(n > 1) System.out.println(n + " " + 1);
	}

输入
24
输出
2 3
3 1

3.埃氏筛选法

找出1到100之间的质数的方法可以根据第一种判断质数的方法循环判断100次，还有一种方法就是唉氏筛选法。

算法介绍：先建立一个数组，0表示质数，1表示合数。从2开始找质数，找到一个质数则把2的倍数的数都变成1，然后3开始找质数，把3的倍数的数都变成1…

例如找出1到18之间的质数

先筛选掉2的倍数，4，6，8，10，12，14，16，18，然后筛选掉3的倍数，6，9，12，15，18，然后筛选掉5的倍数，10，15，以此类推循环到18。

	static int st[] = new int [100];        //0表示质数，1表示合数
	static int n;
	public static void E(int n) {
		for(int i=2;i<=n;i++) {
			if(st[i]==0)                    //第一轮，2开始，4，6，8，10，12...20被筛选
			{                               //第二轮，3开始，6，9，12，15，18被筛选
				for(int j=2*i;j<=n;j+=i)    //第三轮，5开始，10，15，20被筛选
					st[j]=1;
				}
		}
	}