준카판다

https://www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 처음에는 내가 생각한 방식으로 해결하려 했다. 하지만, 문제를 보니까 더 쉬운 방법이 존재했다. 그 사실을 알고 두 가지의 방법으로 문제를 해결하였다. 문제를 보면 소수로만 나눠지는 값을 찾고, 그 나눠진 소수의 값이 몇번 곱해졌는지 출력해야 한다. 나는 2가지의 방법으로 문제를 접근하였다. 방법 1. 먼저 소수를 모두 구하고, 소수인 값으로 입력된 값이 나누어 지면 몇번 나누어 지는지 확인한 후, 출력해준다. 하지만, 방법 2를 보고 방법 1을 보면 소수를 구할 ..

수학에서는 에라토스테네스의 체는 소수를 찾는 방법이다. 체. 걸러내는 이미지가 있다. 계속 걸러내서 소수를 찾는 방법이다. 자. 이렇게 걸러서 흰색 배경 숫자들이 소수가 된다. 그러면 100까지 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 된다. 자. 여기에서 의문점이 들 수 있다. 왜 11, 13은 확인 안하는가? 한번 넣어보자. 11 * 2 / 11 * 3 / ... / 11 * 9 -> 전부 색이 이미 칠해져 있다. 이유는 알 것이다. 2, 3, 5, 7을 지우면서 이미 다 지웠던 숫자들이다. 그러니까 소수를 판별할 때 11 * 11부터 색을 칠하면 되는 것이다. 하..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 나는 지금까지 소수를 찾는 방법은 그 수의 약수를 하나하나 살펴보고 나눠지는 수가 없는 경우를 소수인 경우로 찾았다. 하지만, 이 문제의 경우 주어지는 수가 많다. 비록 100개 이하로 주어져 있긴 하지만, 만약 100개 이하가 아닌 더 큰 수가 입력으로 들어온다면 나는 문제를 어렵게 해결할 것이다. 이 문제를 해결하고 알고리즘 분류를 확인하였다. 낯선 단어가 보였다. 에라토스테네스의 체. 문제를 해결하고 에라토스테네스의 체를 이용한 코드도 소개하도록 하겠다. 처음..