에라토스테네스의 체
[BOJ] 1929 소수 구하기 (Python / 파이썬)
[BOJ] 1929 소수 구하기 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/1929 M이상 N이하의 소수를 모두 출력하는 문제이다. 🛠 풀이 이 문제는 '에라토스테네스의 체' 를 이용해 해결할 수 있다. Step 1. 에라토스테네스의 체를 이용해 소수를 판별한다. 에라토스테네스의 체 : 소수를 판별할 범위만큼 배열을 할당하고 그 인덱스에 해당값을 넣어준 후에, 2부터 시작해서 그 값이 True라면 그 수의 배수에 해당하는 숫자들을 모두 False로 바꿔주는 것을 반복해 대량의 소수를 한꺼번에 판별하는데 용이한 알고리즘이다. 🖊 나의 코드 import sys input = sys.stdin.readline def is_prime(x, y): prime_num = [True] * (y+1) for i ..