문제

소수 찾는 과정은 에라토스테네스의 체를 구현하면 돼 쉬웠는데, 순열이나 조합을 직접 구현해본 경험이 많이 없어 부분집합 구하기가 좀 어려웠다. 그래도 이번에 배웠으니까 다음에는 풀 수 있을 듯함..!

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

bool check[8];
bool isPrime[10000000];
vector<int> numberset;
string str = "";

void makeNumber(int depth, int limit, string numbers) {
	int i;

	if (depth == limit) return;

	for (i = 0; i < limit; i++) {
		if (!check[i]) {
			check[i] = true;
			str += numbers[i];
			numberset.push_back(stoi(str));
			makeNumber(depth + 1, limit, numbers);
			str.pop_back();
			check[i] = false;
		}
	}
}

void calcPrime() {
	int i, j;
	int largest = numberset[numberset.size() - 1];

	memset(isPrime, true, sizeof(isPrime));

	isPrime[0] = false;
	isPrime[1] = false;
	for (i = 2; i * i <= largest; i++) {
		if (isPrime[i]) {
			for (j = i * 2; j <= largest; j += i) isPrime[j] = false;
		}
	}
}

int solution(string numbers) {
	int answer = 0;

	makeNumber(0, numbers.size(), numbers);

	sort(numberset.begin(), numberset.end());
	numberset.erase(unique(numberset.begin(), numberset.end()), numberset.end());

	calcPrime();

	for (int num : numberset) {
		if (isPrime[num]) answer++;
	}

	return answer;
}