import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
private static boolean Debug = true;
private static int PrimeCount;
static int[] pocket;
static HashSet<String> primeSet;
private static int NumberLen;
private static int T;
public static void main(String[] args) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");
FileReader reader = new FileReader(f);
br = new BufferedReader(reader);
} else {
br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용
}
StringTokenizer st;
int TestLen = Integer.parseInt(br.readLine());
for (T = 0; T < TestLen; T++) {
String NumberStr = br.readLine();
NumberLen = NumberStr.length();
pocket = new int[NumberLen];
for (int i = 0; i < NumberLen; i++) {
pocket[i] = NumberStr.charAt(i) - '0';
}
// 탐색 리스트 초기화
primeSet = new HashSet();
findPath(0, "");
primeSet.remove("");
PrimeCount = 0;
for (String item : primeSet) {
// 소수라면 PrimeCount++
isPrime(Integer.parseInt(item));
}
// 소수의 개수 출력
System.out.println(PrimeCount);
}
}
// 소수 판별
private static boolean isPrime(int num) {
// 2 ~ 제곱근까지 검색
int end = (int) Math.sqrt(num);
for (int i = 2; i <= end; i++) {
if (num % i == 0) {
return false;
}
}
// 2보다 작으면 안되!
if (num < 2) {
return false;
}
PrimeCount++;
return true;
}
private static void findPath(int check, String input) {
// 중복되는 경우는 제거
if (primeSet.contains(input)) {
return;
} else {
primeSet.add(input);
}
// 0인 비트를 골라 1로 채운뒤, 문자열을 조립한다.
for (int i = 0; i < NumberLen; i++) {
int using = 1 << i;
// 시작은 0을 제외한다.
if (check == 0 && pocket[i] == 0) {
continue;
}
if ((check & using) == 0) {
findPath(check + using, input + pocket[i]);
}
}
}
public static void log(String input) {
if (Debug) {
System.out.println(input);
}
}
public static void log(String input, Object... args) {
if (Debug) {
System.out.println(String.format(input, args));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
[스크랩] MD5 (위키백과) (0) | 2018.06.04 |
---|---|
1767. [SW Test 샘플문제] 프로세서 연결하기 (0) | 2017.10.21 |
백준 14500번: 테트로미노 (0) | 2017.10.20 |
백준 13460번: 째로탈출2 (0) | 2017.10.20 |
백준 12100번: 2048(Easy) (0) | 2017.10.19 |