목록4948 (1)

파이톨치

[백준][python][4948] 에라토스테네스의 체

[문제] [출처 및 링크] https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net [어떻게 풀까?] 이 문제는 에라스토테네스의 체를 이용해야 풀 수 있다. 이것을 써야 시간 복잡도가 작아지기 때문이다. 에레스토테네스의 체에 대한 개념은 다음 그림과 같다. 만약 2가 소수라면 2의 배수에 해당하는 수들을 모두 지워준다. 만약 3이 소수라면 3의 배수에 해당하는 수들을 모두 지워준다. 그렇게 되면 남은 수들은 모두 소수라는 이야기 이다. 이것을 코드로 구현하기 위해서는 수의 범위가 정해..
알고리즘 2021. 7. 15. 22:25
이전 Prev 1 Next 다음