프로그래밍 공부 노트

에라토스테네스의 체는 소수 판정에 쓰이는 아주 기본적인 기법으로, 1부터 모든 자연수를 적어둔 표에서 2부터 탐색을 시작해, 지워지지 않은 수를 발견한다면 그 수의 1배를 제외한 모든 수를 표에서 제거한다. 이 과정을 어떤 수 k까지 반복했다면 k 이하의 모든 수에 대해 그 수의 배수가 표에서 제거되었으므로, 적어도 k 이하의 모든 소수가 표에 적혀있게 된다. https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 에라토스테네스의 체를 이용해 소수를 구한 뒤, 각 테스트 케이스의 입력 n에 대해 n / 2부터 합이 n이 되는 두 소수 a, n - a를 찾아 출력한다. #include #define SIZE 10000 // prime[i]: i가 소수라면 false, 아니라면 true bool prime[SIZE + 1] = { 1, 1, }; void test_case() { // n: ..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net n의 최대치인 123456을 MAX_N이라 하자. 1부터 2 * MAX_N까지 에라토스테네스의 체를 실행한 뒤, 다시 1부터 2 * MAX_N까지 소수의 개수를 1차원 배열에 각각 저장하면 각 테스트 케이스에 대해 답을 상수 시간 안에 출력할 수 있다. 이 때 1부터 k까지의 소수의 개수 num_k를 알고 있다면, 1부터 k + 1까지의 소수의 개수는 num_k에 k + 1이 소수인지 여부..

https://www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net N의 크기가 작으므로 일일이 인수와 그 차수를 구해도 빠르게 문제를 풀 수 있다. #include void test_case() { // N: 인수를 계산할 수, cnt: 각 인수의 차수 int N, cnt; // N을 입력받은 뒤 scanf("%d", &N); // 2부터 차례로 인수를 계산 for (int i = 2; N > 1; i++) { // 인수의 차수를 초기화한 뒤 cnt = 0; // N이 i로 나누어 떨어질 때마다 while (!(N % i)) { ..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 2부터 1000까지 에라토스테네스의 체를 실행한 뒤, 각 입력받는 수가 소수인지를 세어 소수의 개수를 출력하는 문제이다. #include #define MAX 1000 // prime[i]: i가 소수라면 false, 아니라면 true bool prime[MAX + 1]; int main() { // N: 입력받을 수의 개수, buf: 각 수를 입력받을 버퍼 // ans: 입력받은 수 중 소수의 개수 int N, buf, ans = 0; // 0과 1은 소수가 아니..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 전형적인 에라토스테네스의 체 문제이다. 1부터 N 사이의 소수를 구한 뒤, M부터 N까지의 소수를 출력하면 된다. #include #define MAX_N 1000000 // era[i]: i가 소수라면 false, 아니라면 true bool era[MAX_N + 1] = { true, true, }; int main() { // M, N : 소수의 범위, k : 소수를 구할 때 쓸 곱셈수 int M, N, k; scanf("%..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 배열의 특정 값을 가리키는 두 포인터 l, r이 있다고 하자. l부터 r까지의 부분합 s에 대해, s가 S 미만이라면 r을 1 늘리고, 그렇지 않다면 l을 1 늘리며 연속합을 갱신한다면 빠른 속도로 연속합의 최소 길이를 구할 수 있다. #include using namespace std; #define MAX_N 100000 int min(int a, int b) { return a..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 우선 에라토스테네스의 체로 소수를 구했다고 가정하자. 소수의 연속합으로 N을 구하는 데에 성공했다면, 새로운 연속합을 처음부터 구하는 대신 연속합에서 가장 큰 소수의 다음 소수를 더해 새로운 연속합을 만들고, 이 연속합이 N보다 작거나 같아질 때까지 연속합에서 가장 작은 소수들을 빼가는 식으로 기존의 연속합을 이용할 수 있다. 이 과정을 연속합이 N보다 크거나 같은 소수 하나로만 이루어질 때까지 반복하면 구하고자 하는 소수의 연속합의 개수를 얻을 수 있다. #include #include using namespace..

https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 제곱ㄴㄴ수가 몇 www.acmicpc.net 에라토스테네스의 체를 응용한 문제이다. 에라토스테네스의 체는 1차원 배열의 모든 인덱스에 대해, 소수임을 나타내는 값을 발견하면 그 인덱스에 정수배를 한 모든 인덱스의 값에 소수가 아님을 나타내는 값을 할당한다. 마찬가지로, 이 문제에서는 모든 인덱스에 대해 제곱 ㄴㄴ 수임을 나타내는 값을 발견하면, 그 인덱스에 정수배를 한 모든 인덱스의 값에 제곱 ㄴㄴ 수가 아님을 나타내는 값을..