[c++/프로그래머스] 소수 찾기

문제 링크

소수 찾기

풀이

재귀랑 완전탐색으로 푸는 문제
1. 재귀 함수로 모든 숫자의 경우의 수를 만들고 set에 넣어 중복 처리한다.
2. 만들어진 숫자가 소수인지 체크하는데 제곱근까지 나누면 알 수 있다.
3. flag 처리를 해서 나누어지거나 0, 1일 경우는 소수가 아니므로 false
3-1. 소수라면(true) answer++ 해준다.

코드

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

using namespace std;

string numbers;
set<int> allNum;

void func(vector<int> visit, string curNum)
{
    for(int i=0;i<visit.size();i++)
    {
        if(visit[i]==1) continue;
        vector<int> curVisit = visit;
        curVisit[i] = 1;
        allNum.insert(stoi(curNum+numbers[i]));
        func(curVisit, curNum+numbers[i]);
    }
}

int solution(string numbers) {
    int answer = 0;
    ::numbers = numbers;
    
    vector<int> visit(numbers.size());
    func(visit, "");
    
    for(auto u:allNum)
    {
        bool flag = true;
        if(u==0 || u==1) flag = false;
        for(int i=2;i<=sqrt(u);i++)
        {
            if(u%i==0) 
            {
                flag = false;
                break;
            }
        }
        if(flag) answer++;
    }
    
    return answer;
}