알고리즘
에라토스테네스의 체
Themion
2022. 1. 22. 10:29
에라토스테네스의 체는 소수 판정에 쓰이는 아주 기본적인 기법으로, 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번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net