코딩테스트/백준
[백준-자바] 1929번 소수 구하기 (에라토스테네스의 체) / 2022.02.07
강원대목동녀
2022. 2. 7. 15:56
728x90
https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
* 에라토스테네스의 체
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서
ko.wikipedia.org
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
// 소수이면 false 소수가 아니라면 true
boolean sosu[] = new boolean[n+1]; // boolean 형 배열 생성
sosu[1] = true; // 1이면 소수가 아님 -> true
for(int i=2; i*i<=n; i++) // i가 2부터 n의 절반까지만 (에라토스테네스의 체)
if(!sosu[i]) // 배열에 저장된수가 false일 경우
for(int j=i*i; j<=n; j+=i) // i가 2라면 j는 4, 6, 8, 10 i가 3이라면 j는 6, 9, 12, 15
sosu[j] = true; // 배수는 소수가 아님 -> true
for(int i=m; i<=n; i++){ // 우리가 궁금한 범위는 m이상 n이하
if(!sosu[i]) // 범위 중에 false만 출력 (false가 소수)
System.out.println(i);
}
}
}
자기 자신은 빼고 배수만 다 지워주면 됨
2라면 2는 뺴고 4 6 8 10은 다 지워주고 3이라면 3 6 9 12
4라면 2의 배수에서 지워 졌으므로 생략 -> 5로 넘어가서 10 15 20 25
728x90