📌 문제

[1929] 소수 구하기

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

⬇️ 입력

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

⬆️ 출력

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

💡 코드

❌ 소수를 찾는 알고리즘은 기본적으로 이전 문제의 ➕ 코드와 같은 알고리즘을 사용하였다. 입력받은 a와 b 사이의 소수를 구해야 하기 때문에 바깥쪽 for문의 조건식을 a부터 b까지 돌게 하였고, 소수 판별 변수 isPrime이 true인 경우에만 출력하도록 하였다.

전체적인 알고리즘의 흐름은 맞는 것 같은데 오답 처리가 돼서 뭔가,, 했는데 원인 2개를 금방 찾을 수 있었다!,,.

1. a 이상 b 이하의 소수를 출력해야 하는데, 아래 코드의 경우 for문의 조건식이 b-1까지 돌기 때문에 b가 소수인 경우에 b를 잡아내지 못한다.

2. i가 1인 경우 걸러내는 조건식이 없어서 그대로 출력해버린다.

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		StringBuilder sb = new StringBuilder();
		boolean isPrime = false;
		for(int i=a;i<b;i++) {
			isPrime = true;
			for(j=2;j<=Math.sqrt(i);j++) {
				if(i % j == 0) {
					isPrime = false; break;
				}
			}
			if(isPrime) sb.append(i).append("\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

✅ 위에서 발견한 원인 2가지를 수정하니까 정답 처리 됐다!

1. for문이 b까지 돌 수 있도록 조건식에 등호 추가
2. i가 1인 경우를 걸러낼 수 있도록 조건식 추가

...

for(int i=a;i<=b;i++) {
	if(i == 1) continue;
    
...