[백준] 1929 : 소수 구하기(JAVA)

1929 자바

에라토스테네스의 체 자바

소수 구하기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

209263

59135

41704

26.581%

문제

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

입력

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

출력

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

예제 입력 1 복사

3 16

예제 출력 1 복사

3
5
7
11
13

출처

• 데이터를 추가한 사람: jinjean0123, yongjun042

알고리즘 분류

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

---

처음에는 그냥 구했다가 런타임 에러만 떴따..

소수는 에라토스테네스의 체로 구해야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1929_Eratosthenes {
	static StringBuilder sb = new StringBuilder();

	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());

		boolean[] prime = new boolean[N + 1];
		// 1은 소수가 아니므로 제외
		prime[0] = prime[1] = true;

		for (int i = 2; i <= N; i++) {

			if (prime[i] == true) // 소수가 아니라면 계속!
				continue; // 소수가 아니라면 continue

			for (int j = 2 * i; j <= N; j += i)
				prime[j] = true; // 소수의 배수는 소수를 약수로 가지므로 제외
		}

		// 소수 개수 구하기
		for (int i = M; i <= N; i++) {
			if (!prime[i])
				sb.append(i).append("\n");
		}

		System.out.println(sb);
	}
}

 

답은 맞았으나 런타임 에러 뜬 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1929_Runtime {

	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());

		for (int i = M; i < N; i++) {
			solution(i);
		}

	}

	static void solution(int num) {
		StringBuilder sb = new StringBuilder();

		if (num < 2) {
			return;
		}

		if (num == 2) {
			sb.append(num);
			return;
		}

		for (int i = 2; i < num; i++) {
			if (num % i == 0)
				return;
		}
		sb.append(num);
		System.out.println(sb);
		return;

	}

}