[알고리즘] c++, cpp 소수 찾기

포인트

1.  에라토네스 체, 소수 판별하는 방법

2. 조합을 구하는 방법

 

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

using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<int> v;
    for(auto ele : numbers) v.push_back(ele-'0');
    sort(v.begin(), v.end());

    vector<int> ans;
    do {
        for (int i = 0; i <= v.size(); i++) {
            int temp = 0;
            for (int j = 0; j < i; j++) {
                temp = (temp * 10) + v[j];
                ans.push_back(temp);
            }
        }
    } while(next_permutation(v.begin(), v.end()));

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    for (int i = 0; i < ans.size(); i++) {
        if (isPrime(ans[i])) answer += 1;
    }
    return answer;
}