초보 개발자의 이야기, 릿허브

1. 문제이해 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 다음과 같은 규칙을 따르되, N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 구현하는 것이 목표이다. 1. 2부터 N까지 모든 정수를 적는다. 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. 2. 문제풀이 2부터 N까지의 자연수를 입력받고, K번째 지워지는 숫자를 찾는 문제..

1. 문제이해 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net M 이상 N 이하의 자연수 중 소수인 것을 찾아 해당 값들의 합과 값들 중 최솟값을 출력하는 것이 목표이다. 2. 문제풀이 M 이상 N 이하의 소수를 모두 찾아 해당 값들의 합과 최솟값을 출력하는 문제이다. 이전에도 비슷한 문제를 풀이한 적이 있어서, 해당 방법과 비슷한 방법으로 풀이했다. 제곱근 값(루트값)을 기준으로, 앞의 있는 수들과 뒤에 있는 수들은 서로 짝을 이루므로, 제곱근 값을 기..

1. 문제이해 4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 입력받은 자연수 n에 대해 n보다 크고, 2n보다 작거나 같은 수 중 소수의 개수를 출력하는 것이 목표이다. (입력의 마지막에는 0이 주어진다.) 2. 문제풀이 주어진 n에 대해, n n; count = 0; if (n == 1) {// n이 1인 경우 count = 1; } else { for (int i = n + 1; i

1. 문제이해 1929번: 소수 구하기 (acmicpc.net) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 자연수 M과 N이 주어졌을 때, M과 N 사이의 소수를 모두 출력하는 것이 목표이다. 2. 문제풀이 자연수 M과 N 사이의 소수들을 오름차순으로 출력하는 것이 목표이다. 이전에 입력받은 자연수들 중 소수의 개수를 출력하는 문제를 푼 적이 있는데, 그와 유사한 방법으로 풀이했더니 시간초과가 발생했다. 풀이한 첫 번째 방법은 다음과 같다. for문을 통해, N부터 M까지의 수들을 2부터 자기자신 전까지 나누어보고, 그 중 나누어떨어지..

1. 문제이해 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 수의 개수와 숫자들을 입력받아, 해당 숫자들 중 소수가 몇개인지를 출력하는 알고리즘을 구현하는 것이 목표이다. 2. 문제풀이 문제 그대로, 숫자들을 입력받아, 그 중 소수의 개수를 출력하는 것이 목표이다. 여기서 소수란, 1과 자기 자신만을 약수로 가지는 수를 이야기한다. 따라서, 1보다 큰 수 중에서 1과 자기자신이 아닌 다른 숫자로 나누어지면, 그 수는 소수가 아닌 것이다. (이를 합성수라고한다.) 이 점에 착안하여, 해당 숫자를 1. 2부터 자기..