소수

[백준/Java] 소수 구하기

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 내 풀이 에라토스테네스의 체를 사용합니다. for문 범위를 M 부터 N까지로 설정해주어 M이상 N이하의 소수를 구할 수 있습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I..

[파이썬] 소수 판별 '에라토스테네스의 체'

에라토스테네스의 체 1. 소수를 구하고자 하는 범위를 2부터 나열 2~n 사이의 소수를 구하고자 할 때 다음과 같이 나열합니다. 0과 1은 False로 두고, 2~n-1개까지 True로 둡니다. a = [False,False] + [True]*(n-1) 2. 2부터 나열한 수까지 반복하며 배수 지우기 2부터 n+1까지 반복문을 돌리고 a의 i 번째 인덱스가 True 이면 primes 리스트에 추가합니다. 만약 n=10, i= 2이면, 현재 a[2]는 True이므로 primes에 2를 추가하고 2의 배수인 4,8이 False가 됩니다. 3도 primes에 추가되고 배수인 6,9가 False가 됩니다. 4는 2의 배수를 지우는 단계에서 False가 되었으므로 if문을 통과하지 못합니다. 5는 True 이므로..