[알고리즘] cpp 소수 찾기

포인트

1. 문자열 -> 숫자

2. 10*일의 자리 10*일의 자리

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool chk(int n) {
    if (n >= 2) {
        for (int i = 2; i * i <= n; i++) { // 에라토네스 체 가능
            if (n % i == 0) return false;
        }
        return true;
    } else return false;
}

int solution(string numbers) {
    int answer = 0;
    vector<int> v;

    for (char number : numbers) {
        v.push_back(number - '0');
    }

    sort(v.begin(), v.end());
    vector<int> ans;
    // 모든 경우의 수 찾기
    do {
        for (int i = 0; i <= v.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) { //10을 곱하고 1의 자리 추가
                tmp = (tmp * 10) + v[j];
                ans.push_back(tmp);
            }
        }
    } while (next_permutation(v.begin(), v.end()));

    // 중복된 vector값 제외
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end()); // 정렬을 해야 사용가능하다.

    // 소수 찾기
    for (auto ele : ans) {
        if (chk(ele)) answer += 1;
    }

    return answer;
}