[BOJ/JAVA] 백준 1929 : 소수 구하기 (자바)

문제 정보

  문제명   - 소수 구하기
  난이도   - 실버 III
문제 번호 - 1929번

---

문제 링크

BOJ_S3_1929_소수_구하기

1929번: 소수 구하기

---

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

---

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
3 16	3 5 7 11 13

---

알고리즘 분류

● 수학
● 정수론
● 소수 판정
● 에라토스테네스의 체

---

소스코드

package Lv2_Silver;

import java.util.Arrays;
import java.util.Scanner;
/**
 * @author HanHoon
 * @category 수학, 정수론, 소수 판정, 에라토스테네스의 체
 * https://www.acmicpc.net/problem/1929
 */
public class BOJ_S3_1929_소수_구하기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// M이상 N이하의 수
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		boolean[] arr = new boolean[N+1];
		Arrays.fill(arr, true);
		arr[0] = false;
		arr[1] = false;
		
		for (int i = 2; i <= N; i++) {
			if(!arr[i]) continue;
			for (int j = i+i; j <= N; j+=i)
				arr[j] = false;
		}
		
		for (int i = M; i <= N; i++) {
			if(arr[i])
				System.out.println(i);
		}
		sc.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---