你好呀，我是灰小猿，一個超會寫bug的程式猿！

歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！

標題：組素數

素數就是不能再進行等分的數，比如：2、3、5、7、11等

9=3*3 說明它可以3等分，因而不是素數

我們國家在1949年建國，如果只給你1、9、4、9這4個數字卡片，可以隨意擺放它們的先后順序，（但卡片不能倒著擺放啊，我們不是在做腦筋急轉彎）

那么你能組成多少個4位的素數呢？

比如1949、4919都符合要求

請你提交能組成的4位素數的個數，不要羅列這些素數！！

注意：不要提交解答程序，或其他的輔助說明文字

考察重點：

遞回和回溯演算法下對元素的全排列、素數的判斷、重復元素的去重

在這道題中我們需要重點掌握的就是遞回和回溯演算法下對元素的全排列，根據該思想對1、9、4、9這四個數進行全排列，獲取到排列結果，然后對排列結果進行判斷，判斷其是不是素數，之后記錄符合要求的素數的個數即可，

答案原始碼：

package 一三年省賽真題;

import java.util.HashSet;
import java.util.Set;

public class Year2013_t2 {

	static Set<Integer> set = new HashSet<Integer>();	//定義hash集合，存放符合要求的數值
	/**
	 * 陣列元素的全排列
	 * @param arr 資料陣列
	 * @param n	從第幾個元素開始排列
	 * */
	public static void arrange(int[] arr,int n) {
		//如果排列的數值的序號等于陣列的長度，說明最后一個元素已經確定
		if (n==arr.length) {
			int num = arr[0]*1000 + arr[1]*100 + arr[2]*10 + arr[3];
			//如果是素數
			if (check(num)==num) {
				set.add(num);	//將數值添加到集合中，并去重
			}
		}
		for (int i = n; i < arr.length; i++) {
			//數值交換
			int t = arr[n];
			arr[n] = arr[i];
			arr[i] = t;
			
			arrange(arr, n+1);    //確定下一個數值
			
			t = arr[n];
			arr[n] = arr[i];
			arr[i] = t;
			
		}
	} 
	
	/**
	 * 判斷一個數是不是素數
	 * @return 是素數就回傳該數，不是就回傳0
	*/
	private static int check(int num) {
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				return 0;
			}
		}
		return num;
	}


	public static void main(String[] args) {
		int[] array = {1,9,4,9};
		arrange(array, 0);
		System.out.println(set.size());	//輸出存放在集合中的符合要求的資料長度
	}

}