문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
public class Main {
static ArrayList<Integer> arrayList = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] mn = br.readLine().split(" ");
for(int i = Integer.parseInt(mn[0]); i<=Integer.parseInt(mn[1]); i++) {
if(i == 1) {
continue;
}
if(i%2==0) {
if(i==2) {
bw.append(i + "\n");
arrayList.add(2);
}
else continue;
}
else {
if(checkNum(i)) {
bw.append(i + "\n");
}
}
bw.flush();
}
bw.close();
}
static boolean checkNum(int x) {
for(int o = 0; o<arrayList.size(); o++) {
if(x%arrayList.get(o) == 0) {
return false;
}
}
for(int i = 3; i<=Math.sqrt(x); i+=2) {
if(x%i == 0) {
return false;
}
}
return true;
}
}
소수를 구하는 방법은 여러가지가 있다
내가 사용한 방법은 일단 2의배수를 제외시키고, 소수가 나오면 리스트에 삽입한다.
다음 판별시 먼저 리스트에 있는 소수로 나누어보고 나누어 떨어지지 않으면
그 숫자의 제곱근 까지 나누어 떨어지는 수가 있는지 판별한다.
내가 푼 풀이도 맞긴 하지만 더욱 시간을 줄이고 싶으면
에라토스테네스의 체 라는 방법이 있다.
나도 구글 검색으로 공부하게 되었는데 매우 자세하고 이해가 쉽게 설명이 되어있다.
'백준문제풀이' 카테고리의 다른 글
백준 1874 자바(java) 스택 수열 (0) | 2021.03.02 |
---|---|
백준 10828 자바(java) 스택 구현 (0) | 2021.03.02 |
백준 1181 자바(java) 단어 정렬 (0) | 2021.03.02 |
백준 10816 자바(java) 숫자카드 2 (0) | 2021.03.02 |
백준 9012 자바(java) 괄호 (0) | 2021.03.02 |