-
1929 - 소수 구하기알고리즘 2023. 5. 24. 20:50728x90
https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
문제요약
- M이상 N이하의 소수를 모두 출력
- 1 ≤ M ≤ N ≤ 1,000,000
import java.io.*; public class Main { public static boolean[] getPrime() { int num = 1000000; boolean[] arr = new boolean[num + 1]; // 1은 소수 아님 arr[1] = true; for (int i = 2; i * i < arr.length; i++) { // false = 소수 if (!arr[i]) { for (int j = i * i; j < arr.length; j += i) { arr[j] = true; } } } return arr; } public static void main(String[] args) throws IOException { boolean[] arr = getPrime(); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String nums = reader.readLine(); int start = Integer.parseInt(nums.split(" ")[0]); int end = Integer.parseInt(nums.split(" ")[1]); for (int i = start; i <= end; i++) { if (!arr[i]) { bw.write("" + i); bw.newLine(); bw.flush(); } } bw.close(); reader.close(); } }
느낀점
소수 구하기 문제는 전 날에 에라토스테네스의 체를 사용해서 구하는 것을 알았다.
이전에 풀어서 알아낸 지식으로 다음 문제에 적용해서 쉽게 풀리니 매우 재밌었다.
계속 달려보자!
'알고리즘' 카테고리의 다른 글
1011 - Fly me to the Alpha Centauri (0) 2023.05.24 1110 - 더하기 사이클 (2) 2023.05.24 10250 - ACM 호텔 (0) 2023.05.24 2869 - 달팽이는 올라가고 싶다 (0) 2023.05.23 4948 - 베르트랑 공준 (0) 2023.05.23