Java質(zhì)數(shù)算法是什么？動(dòng)力節(jié)點(diǎn)小編來(lái)為大家解答。質(zhì)數(shù)就是一個(gè)數(shù)只可以被它自己和1整除(1不是質(zhì)數(shù))

1.判斷一個(gè)數(shù)是不是質(zhì)數(shù)

只需要讓這個(gè)數(shù)循環(huán)除以2到根號(hào)n的數(shù) 如果出現(xiàn)整除的現(xiàn)象，則不是質(zhì)數(shù)，反之則為質(zhì)數(shù)

源代碼：

	public static int F(int x) {   //判斷是否為質(zhì)數(shù) 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;
	}

除了判斷是否是質(zhì)數(shù)，我們還可以分解質(zhì)因數(shù)

2.分解質(zhì)因數(shù)

根據(jù)算術(shù)基本定理又稱唯一分解定理，對(duì)于任何一個(gè)合數(shù)， 我們都可以用幾個(gè)質(zhì)數(shù)的冪的乘積來(lái)表示。

算法邏輯描述：循環(huán)找質(zhì)因數(shù)，找到時(shí)循環(huán)繼續(xù)除以這個(gè)數(shù)，記錄個(gè)數(shù)，直到不整除時(shí)退出循環(huán)繼續(xù)找下一個(gè)質(zhì)因數(shù)，如果最后n不是1，說(shuō)明還有最后一個(gè)質(zhì)因數(shù)也就是它本身n，輸出出來(lái)。

源代碼：

	public static void prime(int n){
	    for(int i = 2; i <= n / i; i++){      循環(huán)到根號(hào)n為止
	        int a = 0, b = 0;
	        while(n % i == 0){                如果可以整除說(shuō)明是質(zhì)因數(shù)
	            a = i;
	            n /= i;                       一直除以這個(gè)數(shù)直到不整除為止
	            b++;                          累計(jì)a的個(gè)數(shù)
	        }
	        if(b > 0)
	            System.out.println(a + " " + b);
	    }
	    if(n > 1) System.out.println(n + " " + 1);
	}

輸入
24
輸出
2 3
3 1

3.埃氏篩選法

找出1到100之間的質(zhì)數(shù)的方法可以根據(jù)第一種判斷質(zhì)數(shù)的方法循環(huán)判斷100次，還有一種方法就是唉氏篩選法。

算法介紹：先建立一個(gè)數(shù)組，0表示質(zhì)數(shù)，1表示合數(shù)。從2開(kāi)始找質(zhì)數(shù)，找到一個(gè)質(zhì)數(shù)則把2的倍數(shù)的數(shù)都變成1，然后3開(kāi)始找質(zhì)數(shù)，把3的倍數(shù)的數(shù)都變成1…

例如找出1到18之間的質(zhì)數(shù)

先篩選掉2的倍數(shù)，4，6，8，10，12，14，16，18，然后篩選掉3的倍數(shù)，6，9，12，15，18，然后篩選掉5的倍數(shù)，10，15，以此類推循環(huán)到18。

	static int st[] = new int [100];        //0表示質(zhì)數(shù)，1表示合數(shù)
	static int n;
	public static void E(int n) {
		for(int i=2;i<=n;i++) {
			if(st[i]==0)                    //第一輪，2開(kāi)始，4，6，8，10，12...20被篩選
			{                               //第二輪，3開(kāi)始，6，9，12，15，18被篩選
				for(int j=2*i;j<=n;j+=i)    //第三輪，5開(kāi)始，10，15，20被篩選
					st[j]=1;
				}
		}
	}