소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839
가능한 숫자의 경우의 수를 모두 만들어서 그 수가 소수 인지 판단합니다.
가능한 모든 숫자를 만들기 위해 next_permutation을 이용하여 모든 경우의 순열을 만듭니다.
- next_permutation을 이용하면 쉽게 모든 경우의 수를 만들 수 있습니다.
소수를 판단하기 위해서는 에라토스테네스의 체를 사용합니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <set>

using namespace std;

int n = 100000000;
const int MAX_N = 100000000;
bool isPrime[MAX_N + 1];

void eratosthenes() {
	memset(isPrime, 1, sizeof(isPrime));
	//1은 항상 예외 처리
	isPrime[0] = isPrime[1] = false;
	int sqrtn = int(sqrt(n));
	for (int i = 2; i <= sqrtn; ++i)
		//이 수가 아직 지워지지 않았다면
		if (isPrime[i])
			//i의 배수j들에 대해 isPrime[j]=false로 둔다.
			//i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
			for (int j = i * i; j <= n; j += i)
				isPrime[j] = false;
}

bool next_k_permutation(string& s, int k) {
	sort(s.begin() + k, s.end(), greater<char>());
	return next_permutation(s.begin(), s.end());
}

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

	set<int>s;
	for (int i = 1; i <= numbers.size(); ++i) {
        sort(numbers.begin(), numbers.end());
		do {
			int n = stoi(numbers.substr(0, i));			
			if (isPrime[n]) {
				if (s.count(n) == 0) {
					answer++;
					s.insert(n);
				}
			}
		} while (next_k_permutation(numbers, i));
	}

	return answer;
}