[프로그래머스] Level.2 완전탐색- 소수찾기

코딩테스트 연습 - 소수 찾기

 

문제설명

 

입출력예

 

 

 

 

 

https://yabmoons.tistory.com/336 분의 소수찾기와 순열 조합게시물을 참고해서 풀었다 ㅠㅠ

[ 프로그래머스 소수 찾기 (Lv2) ] (C++)

 

#include<string>
#include<vector>
#include<cmath>

using namespace std;

bool visited[10000000];
bool use[10];
int total;

bool isprime(int n)
{
	if (n == 0 || n == 1) return false;
	for (int i = 2; i <= sqrt(n); i++){
		if (n % i == 0) return false;
	}
	return true;
}

void findNumber(int cnt, string numbers, string temp)
{
	if (temp != "" && visited[stoi(temp)] == false){
		int Num = stoi(temp);
		visited[Num] = true;
		if (isprime(Num) == true) total++;
	}

	for (int i = 0; i < numbers.length(); i++) {
		if (use[i] == true) continue;
		use[i] = true;
		findNumber(cnt + 1, numbers, temp + numbers[i]);
		use[i] = false;
	}
}

int solution(string numbers)
{
	findNumber(0, numbers, "");
	return total;
}