<Programmers>Brute Force_소수 찾기 Finding Prime Numbers c++

Google 아니고 Joogle·2021년 12월 13일
0

Programmers

목록 보기
4/22
post-thumbnail

소수를 구하는 부분은 쉽게 구현할 수 있었는데 모든 순열을 구하고 중복된 값을 제외한는 과정을 구하지 못해서 다른 사람의 코드를 참고 했다.

1. 숫자 n이 들어 왔을 때 소수인지 판별- 에라토스테네스의 체

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

처음에는 for문을 i=2 to i=n-1 까지 돌리는 코드를 작성 하였는데 에라토스테네스의 체 라는 방법을 배웠다.


<위키백과 참조>
1. 소수를 구하고자 하는 구간의 모든 수를 나열
2. 2는 소수 - 2의 배수를 모두 지운다
3. 3은 소수 - 3의 배수를 모두 지운다
4. 5는 소수 - 5의 배수를 모두 지운다
5. 7은 소수 - 7의 배수를 모두 지운다
6. 이 과정을 반복, 구간에 모둔 소수가 남는다
7. 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다

2. 주어진 numbers에 적힌 글자 하나 하나를 char v 에 담는다

    vector<char> v;
    for (int i=0; i<numbers.size(); i++)
        v.push_back(numbers[i]);
    sort (v.begin(), v.end());

3. next_permutation 함수를 사용하여 모든 순열을 구한다

    vector<int> nums;
    do {
        string temp="";
        for (int i=0; i<v.size(); i++) {
            temp.push_back(v[i]);
            nums.push_back(stoi(temp));
        }
    }while (next_permutation(v.begin(), v.end()));

e.g) 0 1 1
next_permutation 함수를 이용하면 while문을 한 번씩 돌 때마다 v에는 0 1 1, 1 0 1, 1 1 0 이 저장된다.
v에 0 1 1 이 저장되었을 때, nums에는 0, 1(01), 11(011)이 push
v에 1 0 1 이 저장되었을 때, nums에는 1, 10, 101이 push
v에 1 1 0 이 저장되었을 때, nums에는 1, 11, 110이 push

4. 정렬을 한 뒤 중복된 순열을 제거한다

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

5. 전체 코드

#include <string>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

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

int solution(string numbers) {
    int answer = 0;
    
    vector<char> v;
    vector<int> nums;
    
    for (int i=0; i<numbers.size(); i++)
        v.push_back(numbers[i]);
    sort (v.begin(), v.end());
    
    do {
        string temp="";
        for (int i=0; i<v.size(); i++) {
            temp.push_back(v[i]);
            nums.push_back(stoi(temp));
        }
    }while (next_permutation(v.begin(), v.end()));
    
    sort (nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()),nums.end());
    
    for (int i=0; i<nums.size(); i++)
        if (isPrimeNumber(nums[i])) answer++;
    
    return answer;
}

profile
Backend 개발자 지망생

0개의 댓글