[Programmers] 소수 찾기(Lv.2)(C++)

풀이 소요시간 : 15분

O(sqrt(N)) 속도의 소수 판독

해당 문제를 풀면서 완전 탐색보다 조금 더 빠른 소수 판독 방법을 공부했다. 2부터 sqrt(N)까지 나누어 떨어지는 수가 하나라도 있다면 소수가 아니라고 할 수 있다. 다만 N이 0이나 1인 경우 예외처리를 반드시 해주어야한다.

전체 코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;

string S;
int Visit[7];
int Ans = 0;
map<int, int> Map;



bool Check(string s) {
    
    int num = stoi(s);
    if(Map[num] > 0 || num <= 1) return false;
    // num = 0 인 경우 반례
    
    Map[num] = 1;

    for(int i = 2; i <= sqrt(num); i++)
    {
        if(num % i == 0) return false;
        //소수가 아니다.
    }
    return true;
    //소수다.
}

void Dfs(string str, int N) {
    if(str.length() == N) 
    {
        if(Check(str) == true) 
        {
            cout << str << endl;
            Ans++;
        }
        return;
    }
    
    //오름차순 아니여도된다.
    for(int i = 0; i < S.length(); i++)
    {
        if(Visit[i] == 1) continue;
        Visit[i] = 1;
        Dfs(str + S[i], N);
        Visit[i] = 0;
    }
    
}


int solution(string numbers) {
    S = numbers;
    int N = S.length();
    for(int i = 1; i <= N; i++) Dfs("", i);
    return Ans;
}