Programmers > 코딩테스트 연습 > 완전탐색 > 소수찾기

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

풀이

일단 먼저 에라토스테네스 방법을 통해 소수인 것과 소수가 아닌것을 bool형 배열에 

구분해놓았다.

bool check[10000000];

void eratosthenes()
{
	for (int i = 2; i <= 1000; i++)
	{
		if (!check[i]) {
			for (int j = i*i; j <= 10000000; j += i)
			{
				check[j] = true;
			}
		}
	}
}

그런다음 주어진 numbers에 대해 각각의 문자를 map에 포함시켰다 

예를들어 numbers = "1234"라면

m['1'] = 2 , m['2'] = 1 이런식이다.

그 후 2부터 pow(10,numbers.size()) 까지 전수조사를 하여

-> 예를들어 nubmers="12"라면 100까지 조사, numbers="12345"라면 100000까지 조사하게 하는 것이다.

map을 활용해 해당 숫자가 우리가 가지고 있는 숫자들로 이루어져 있는 것인지 검사하였다.

int solution(string numbers) {
	check[0] = 1; check[1] = 1;
	eratosthenes();
	map<char, int> m;
	for (int i = 0; i < numbers.size(); i++)
		m[numbers[i]]++;
	int size = numbers.size();
	int limit = (int)pow(10, size);
	int answer = 0;
	for (int i = 2; i < limit; i++)
	{
		string tmp = to_string(i);
		bool b = true;
		map mm = m;
		if (!check[i]) {
			for (int i = 0; i < tmp.size(); i++)
			{
				if (--mm[tmp[i]] < 0) {
					b = false;
					break;
				}
			}
			if (b) answer++;
		}
	}
	return answer;
}