에라토스테네스의 체

📌 문제 주어진 수 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,..
턴태
'에라토스테네스의 체' 태그의 글 목록