[C/C++] programmers Level 2 소수 찾기

 

 

 

 

코드

 

#include <cmath> // sqrt(루트)
#include <string>
#include <algorithm> // sort, next_permutation(순열)
#include <set> // 중복 방지 set

using namespace std;

bool isPrime(int num){ // 소수 검사
    if (num <= 1){ // 2미만 소수는 없다.
        return false;
    } 
        
    for (int i=2; i<=sqrt(num); i++){ // sqet(num) : 계산 시간 절약
        if (num % i == 0){ // 2부터 numbers의 제곱근까지 나눈 나머지가 0이면 소수가 아님
            return false;
        } 
    }
    
    return true; // 위의 조건문에 해당 안되면 소수
}

int solution(string numbers) {
    
    set<int> answer; // 중복 방지를 위한 집합 자료구조 
    int temp=0; // 숫자 조합의 값
    
    sort(numbers.begin(), numbers.end()); // 오름차순 정렬
    
    do {
        for (int i=1; i<numbers.size()+1; i++){
            
            // 가능한 숫자의 조합을 모두 만들기위해 substr로 숫자의 길이를 변형
            temp = stoi(numbers.substr(0, i));
            if (isPrime(temp)){
                answer.insert(temp);
            }
        }
    // next permutation 함수를 이용해 numbers의 값들을 다음 순열로 바꿈
    } while(next_permutation(numbers.begin(), numbers.end()));
    // next_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.
    
    return answer.size();
}