에라토스테네스의 체

📌 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 📌 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 📌 출력 주어진 수들 중 소수의 개수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 에라토스테네스의 체를 사용하여 소수를 쉽게 찾아낼 수 있다. 소수를 찾는 방법에는 여러 가지 방법이 있다. 가장 쉬운 방법은 for문으로 2부터 n까지 탐색해보는 방법이다. def is_prime_number(n): for i in range(2, n): if n % i == 0: return False return True 이 경우 n까지 모두 탐색하는 방법으로 시간복잡도는 O(N)이라고 할 수 있다. 그런..

📌 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 📌 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 소수를 2중 for문으로 구하면 O(N2)이 걸리기 때문에 문제의 최댓값인 106을 제곱했을 때 1012이기 때문에 1000초가량 걸린다. 그런데 소수를 구하는 데에 있어서 그 수를 2부터 자기 자신까지 나누는 것이 아니라 자신의 제곱근만큼만 약수를 구하면 된다. 왜냐하면 제곱근 이후로 나누는 수와 몫이 서로 바뀌어 등장하기 때문이다. 예를 들어 16의 약수는 1, 2, 4, 8,..