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;
				}
		}
	}