문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다. 소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다. 우리는 두 가지 경우로 풀 수 있다. 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

www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 두 포인터를 활용한 재미있는 문제였다. n을 입력받아서 소수 판정을 해주고 prime 배열에 넣어주고 두 포인터를 쓰면 된다. #include #include using namespace std; const int MX = 4000001; vector sieve; vector prime; int s, e, sum, cnt; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i = n) sum -= prime[s++..

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 팰린드롬 수는 어떤 수를 반대로 뒤집고 그 수가 같다면 팰린드롬 수이다. 에라토스테네스의 채를 사용해서 소수를 판단해주고 문자열을 사용해서 뒤집고 체크해주면 되는 쉬운 문제였다. #include #include #include #include using namespace std; vector sieve(1100001); void era(int n) { fill(sieve.b..

www.acmicpc.net/problem/19699 19699번: 소-난다! 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 � www.acmicpc.net 최근에 추가된 문제 중 하나이다. 처음엔 백트래킹으로 풀었는데 안 풀려서 그냥 next_permutation으로 풀었다. 입력받은 수를 정렬시키고 m번만큼 sum변수에 더해줘서 그 sum이 소수이면 ans에 추가해준다. #include #include #include using namespace std; bool vis[10001]; void era() { fill(vis, vis + 10001, true)..