소수 구하기
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
예제 입력 1
3 16
예제 출력 1
3
5
7
11
13
우선 내가 푼 방식.
일단 최소값이 1일경우(M==1) 소수가 아니므로 2로 만들어줬다.
그리고 두 번째 for문에서 2부터 해당 수의 제곱근까지 나눠 떨어지는지 확인해서 isPrime에 소수가 아니면 false값을 담아주었다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
if(M==1) M++;
for (int i = M; i <= N; i++) {
boolean isPrime = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime == true) {
sb.append(i + "\n");
}
}
System.out.println(sb);
br.close();
}
}
아래는 다른 분들 코드를 참조해 수정한 방식. 에라토스테네스의 체 알고리즘을 이용했다.
우선 isPrime 배열을 만들어서 모두 true 값을 넣어주었다. 1은 소수가 아니므로 false를 넣어주었다.
그리고 첫 번째 for문을 이용해 2부터 N의 제곱근 값까지 계산했다. 해당 수의 배수이면 소수가 아니므로 이중 for문에서 i의 배수들에 모두 false 값을 넣어줬다.
첫 번째 for문 아래에 조건문을 주었는데, 만약 isPrime 배열 요소에 이미 false 값이 들어있으면 두 번째 반복문을 실행할 필요가 없기 때문이다. (만약 i=4인 경우 이미 i=2인 경우를 통해 4의 배수들도 모두 처리가 되어있기 때문이다.)
이중 for문의 초기식에는 j=i*i 식을 이용했다.
만약 j가 5일 경우 5*5가 되겠다. 5*2, 5*3, 5*4 의 경우는 이미 j가 2, 3, 4인 케이스에서 모두 계산되었기 때문에 이렇게 초기식을 줬다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[1] = false;
for (int i = 2; i <= Math.sqrt(N); i++) {
if (isPrime[i] == true) { // false 들어있으면 배수 비교할 필요 없음
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
for (int i = M; i <= N; i++) {
if (isPrime[i] == true) {
sb.append(i + "\n");
}
}
System.out.println(sb);
br.close();
}
}
참조
'6. 자료구조 & 알고리즘 > 6-2. 백준' 카테고리의 다른 글
백준 - [2447번: 별 찍기 - 10] (0) | 2022.06.21 |
---|---|
백준 - [4948번: 베르트랑 공준] (0) | 2022.06.19 |
백준 - [11653번: 소인수분해] (0) | 2022.06.19 |
백준 - [1978번: 소수 찾기] (0) | 2022.06.19 |
백준 - [10757번: 큰 수 A+B] (0) | 2022.06.17 |