
[프로그래머스 C++] 소수 찾기
·
알고리즘/Programmers
문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다. 소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다. 우리는 두 가지 경우로 풀 수 있다. dfs로 풀던가 next_permutation으로 풀던가 둘 중 하나로 풀면 된다. 나는 next_permutation으로 풀었다. #include #include #include #include using namespace std; vector sieve; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i