소수 찾기 (feat. 프로그래머스, 42839번)

소수 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <string>
#include <string.h>
#include <set>
#include <cmath>
#include <algorithm>
#define MAX_SIZE        10000000
using namespace std;
bool visit[MAX_SIZE], arr[MAX_SIZE];
set<int> ans;
string str;
void dfs(int count, string& number, int& total) {
    if (count == total) {
        ans.insert(stoi(str));
        return;
    }
    for (int i = 0; i < number.size(); ++i) {
        if (!visit[i]) {
            visit[i] = true;
            str.push_back(number.at(i));
            dfs(count + 1, number, total);
            visit[i] = false;
            str.pop_back();
        }
    }
}
int solution(string numbers) {
    memset(visit, false, sizeof(visit));
    for (int i = 1; i <= numbers.size(); ++i)
        dfs(0, numbers, i);
    memset(arr, false, sizeof(arr));
    arr[0] = arr[1] = true;
    int max_value = *max_element(ans.begin(), ans.end());
    int e = sqrt(max_value);
    for (int i = 2, j; i <= e; ++i)
        if (!arr[i])
            for (j = i << 1; j <= max_value; j += i)
                arr[j] = true;
    int answer = 0;
    for (auto& v : ans)
        if (!arr[v])
            ++answer;
    return answer;
}
// *&)*@*

 

 

1. 입력된 numbers를 문자마다 쪼개어 보았을때, 이를 1자리부터 numbers.size() 만큼 모든 가능한 조합 숫자들을 구합니다. (numbers가 [1,2,3] 이라면 1,2,3,12,21,13,31,23,32,... 와 같은 모든 조합을 구합니다.)
2. "에라토스테네스의 체" 를 이용하여 위 조합으로 구해진 숫자들 중 최대값만큼 소수를 구합니다. (위 예를 본다면 321가 최대값이므로 2부터 321까지의 모든 소수를 구합니다.)
3. 1번에서 구해진 조합들을 하나씩 선택하여 2번에서 구한 소수 배열에 속하는지 체크하고 소수라면 answer 변수를 증가시킵니다.

"에라토스테네스의 체" 는 소수를 가장 빠르게 구할 수 있는 방법입니다.

수식 자체를 외워버리는 것도 크게 도움이 될 수 있습니다.

비슷한 문제가 백준에 있으므로 한 번 풀어보시길 권장합니다.

소수 구하기 (feat. 백준, 1929번)