[프로그래머스 소수 찾기] c++ (풀이,코드)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

문제

 

풀이과정

우선 이 문제는 모든 수의 조합에 대해서 확인을 해야합니다.

 

문제의 예시를 보게 되면 17이면 7 17 71이라는 소수를 만듭니다. 즉 모든 숫자의 조합을 확인해봐야 하기때문에 

algoirthm헤더에서 next_permutation을 사용합니다.

 

또한 모든 조합을 얻었을때 같은 숫자에 대해서는 중복을 제거합니다.

 

진행과정

1. 모든 조합에 대해서 진행 (do~while next_permutation)

2. 모든 조합에 대한 추가한 벡터에 중복 제거 (erase+unique)

3. 소수제거 -> 짝수에 대해서 미리 제거하고 숫자의 제곱근까지의 소수판별을 합니다.

 

#include <string>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

int solution(string numbers) {

    int answer = 0;

   

    vector<int> v;

    vector<int> permutation; //모든 조합들에 대한 백터

   

    for(int i = 0 ; i< numbers.length();i++){

        v.push_back((numbers[i] - '0'));

    }

    sort(v.begin(),v.end());

   

    do{

        int num = 0;

        for(int i = 0; i < v.size();i++){

            num *= 10;

            num += v[i];

            permutation.push_back(num);

        }

    }while(next_permutation(v.begin(),v.end())); //모든 조합에 대해서 진행

   

    sort(permutation.begin(),permutation.end()); //모든 조합들에 대해 정렬

    permutation.erase(unique(permutation.begin(),permutation.end()),permutation.end()); //중복 제거

   

    for(int i = 0; i < permutation.size();i++){

        int PrimeFlag = 1; //소수플래그

        if(permutation[i] < 2)

            continue; // 0혹은 1은 소수아님

        else if(permutation[i] == 2){

            answer++;

            continue;

        }

        for(int j = 2;j<=sqrt(permutation[i]);j++){

            if(permutation[i] % j == 0 || permutation[i] % 2 == 0){

                PrimeFlag = 0;

                break;

            }

        }

        if(PrimeFlag == 1){ //소수일때 ++

            answer++;

        }

    }

    return answer;

}