백준 1929번 자바 문제 답/해설(소수 구하기 문제)

[1] 백준 카테고리
단계별로 풀어보기
기본 수학 2
4단계 1929번 문제
소수 구하기

[2] 문제
1. 입력

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

2. 출력

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

3. 예제 입력 1

3 16

4.예제 출력 1

3

5

7

11

13

[3] 정답

1. 정답 해설 미포함

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int M = sc.nextInt();
		int N = sc.nextInt();

		boolean[] prime = new boolean[N+1];
		prime[0] = true;
		prime[1] = true;
        
		for(int i = 2; i <= N; i++){
			if(prime[i] == false){
				if(i >= M)
					System.out.println(i);
				for(int j = i+i; j <= N; j+=i)
					prime[j] = true;
            }
		}
		sc.close();
    }
}

2. 정답 해설 포함

import java.util.Scanner;
// Scanner 사용을 위해서 java.util.Scanner 클래스를 import 한다.

public class Main {
// 접근제어자 public으로 Main 클래스를 선언한다

	public static void main(String[] args) {
	// 접근제어자 public으로 메모리에 상주하고 리턴값이 없이 main 함수를 선언한다
		Scanner sc = new Scanner(System.in);
		// Scanner 객체 sc를 선언한다.

		int M = sc.nextInt();
		// int형 변수 M를 선언하고 값을 입력받아 저장한다.
		int N = sc.nextInt();
		// int형 변수 N를 선언하고 값을 입력받아 저장한다.

		boolean[] prime = new boolean[N+1];
		// boolean형 배열 prime을 선언하고 배열의 길이를 N+1로 한다
		prime[0] = true;
		// 변수 prime[0]에 true 값을 저장한다
		prime[1] = true;
		// 변수 prime[1]에 true 값을 저장한다
        
		for(int i = 2; i <= N; i++){
		// 2~N까지 괄호의 안의 코드를 반복한다
			if(prime[i] == false){
			// prime[i]가 false이면 괄호안의 코드를 실행한다.
				if(i >= M)
					System.out.println(i);
					// i가 M보다 크면 i 값을 출력한다.
				for(int j = i+i; j <= N; j+=i)
				// i+i~N까지 괄호안의 코드를 반복한다.
					prime[j] = true;
					/* 변수 prime[j] true 값을 저장한다.
					에라토스테네스의 체로 i의 배수를 걸려내는 작업이다.*/
            }
        }
			sc.close();
			// Scanner 객체 sc 사용을 종료한다.
    }
}

 

		for(int i = 2; i <= N; i++){
			if(prime[i] == false){
				if(i >= M)
					System.out.println(i);
				for(int j = i+i; j <= N; j+=i)
					prime[j] = true;

에라토스테네스의 채로 i의 배수를 계속 걸려낸다.

2의 배수, 3의 배수, 4의 배수..... 순으로 걸려내게 된다.