[C++]소수 찾기

1. 문자열을 쪼개서 문자 하나로 저장한 뒤, 조합 가능한 모든 수를 생성한다.

2. 소수 검사 함수를 만든다.

 

1. 조합 가능한 모든 수를 생성하고 중복 제거하여 저장하기

조합 가능한 모든 수를 어떻게 만들지에서 고민을 많이 했다.

algorithm STL의 next_permutation을 쓰면 순열을 만들 수 있다고 한다.

'내림차순'으로 해당값이 정렬을 마칠때까지 순서대로 작업을 진행한다.

그렇기 때문에 모든 경우의 수를 파악하고 싶다면, sort로 오름차순을 만들어주고 next_permutation이 false를 반환할때까지 계속하면 되는 것이다.(이 함수는 작동하지 않으면 false를 반환한다.)

배열뿐만 아니라 string에도 가능하다.

    sort(numbers.begin(),numbers.end());
    do{
        std:: cout << numbers << endl;
    } while(next_permutation(numbers.begin(),numbers.end()));

물론 이것만 하면, 세자리 수의 순열만 반환하고 있기 때문에, 자리수 마다 적당한 문자열을 만들어주고, 이를 순열로 만들어야 한다. 근데 생각해보니까, 저 string에서 필요한만큼 자르면 되지 않나?

그리고 모든 경우의 순열 값을 stoi로 숫자로 만든 다음, unordered 맵에 넣어서 중복을 방지할 것이다.

    int size = numbers.size();
    vector<string> numbersArray;
    unordered_map<int,int> answerMap;
    sort(numbers.begin(),numbers.end());
    do{
        for(int i = 1; i < size+1; i++) { //가능한 자리수만큼
            int temp = stoi(numbers.substr(0,i));
            answerMap[temp] = 1;    //중복 제거해서 저장
        }
    } while(next_permutation(numbers.begin(),numbers.end()));
    for(auto ele : answerMap) {
        cout << ele.first << endl;
    }

여기서 string의 substr을 사용했다. 

그냥 string.substr(n); 을 쓰면 index n부터 끝까지 잘라서 반환하고

string.substr(n,m);을 쓰면 index [n,m] 잘라서 반환한다.

의도한 대로, 중복이 제거되어 map에 잘 저장되어 있다.

이제 이 key값들을 소수검사하면 된다!

 

2. 소수 검사 함수 만들기

소수 검사는 전에 짜본 적이 있어 기억하는대로 진행할 것이다.

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

간단히 말해, 2보다 작거나, 2가 아닌 짝수는 애초에 거른다.

이후 3부터 해당 값의 제곱근보다 작거나 같을 때 까지 2씩 증가시키면서(짝수 제외하기 위함) 나머지 값 체크를 진행한다.

이 모든 검사를 통과하면 true를 반환한다.

 

#include <string>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>

using namespace std;

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

int solution(string numbers) {
    int answer = 0;
    int size = numbers.size();
    vector<string> numbersArray;
    unordered_map<int,int> answerMap;
    sort(numbers.begin(),numbers.end());
    do{
        for(int i = 1; i < size+1; i++) { //가능한 자리수만큼
            int temp = stoi(numbers.substr(0,i));
            answerMap[temp] = 1;    //중복 제거해서 저장
        }
    } while(next_permutation(numbers.begin(),numbers.end()));
    for(auto ele : answerMap) {
        if(isPrime(ele.first))
            answer++;
    }
    return answer;
}