모든 소수 찾기 - 완전 탐색

주어진 문자열을 각각의 숫자로 분리하여 만들 수 있는 모든 경우의 수가 소수인지 아닌지 검사하는 프로그램을 만들어라.

'17' ==> [1, 7, 17, 71] 모든 경우의 수

위의 집합에서 소수만 뽑으면 7, 17, 71이 나온다.

 

위의 프로그램을 구현하기 위해 필요한 지식

1. 소수 검증 함수
2. STL의 순열 알고리즘

소수란?

1과 자기자신으로만 나누어 지는 수를 말한다.

소수를 검증하는 알고리즘을 구현하는 방식

1. 1부터 자기자신의 숫자까지 반복문을 순회하며 나누어 떨어지는지 검사
2. 에라토스테네스?의 체 (이름이 너무 어렵다... 그냥 비스므리한 이름이다. 여하간)

위의 2가지 방식을 잘 섞으면 효율이 좋은 알고리즘을 만들 수 있다.

위의 1번 문항을 보면 자기자신의 숫자까지 반복문을 순회한다고 했는데 사실 여기서는 자기자신의 제곱근까지만 반복해도 된다. (해당 증명은 인터넷에서 찾아보도록...)

 

알고리즘 구현 단계

1. 소수 검증 함수 구현

2. 에라토스테네스의 체 구현

   1. 주어진 숫자의 순열 중 가장 큰 수로 만든다.

3. 순열로 만들어지는 문자열을 1, 2, 3, ..., len(문자열의 길이) 개수로 나눠서 소수 검증을 한다.

   1. 모든 경우의 수 체크
   2. 단점: 중복 검사 발생, 개선 가능

 

bool isPrime(int number)
{
    if (number == 1)
        return false;
    if (number == 2)
        return true;
    if (number % 2 == 0)
        return false;

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

    return isPrime;
}

bool compare(char a, char b)
{
    return a > b;
}

int solution(string numbers) {
    int answer = 0;

    string temp;
    temp = numbers;

	// 소수 체를 위해서 가장 큰 수 만든다.
    sort(temp.begin(), temp.end(),compare);

	// 가장 큰 수 만큼 공간 할당
    vector<bool> prime(std::stoi(temp)+1);

	// 소수 체 만들기
    prime[0] = false;
    for (long long i = 1; i < prime.size(); i++)
    {
        prime[i] = isPrime(i);
    }

    string s, sub;
    s = numbers;

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

	// 중복 수 방지를 위해서 set 사용
    set<int> primes;
    int len = s.size();

    do {
        for (int i = 1; i <= len; i++)
        {
            sub = s.substr(0, i);
            if (prime[std::stoi(sub)])
            {
                primes.insert(std::stoi(sub));
            }
        }
    } while (next_permutation(s.begin(), s.end())); // 순열로 조합 뽑기

    answer = primes.size();
    return answer;
}