Baekjoon1929: 소수 구하기

문제

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

입력

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

출력

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

 

추상화

1) 1,000,001의 크기의 논리배열을 만들고 소수가 아닌 수들을 true로 만든다
2) M, N을 입력받으면 반복문의 범위를 정할 수 있고 해당 배열의 index가 false인 값들만 출력한다

import java.io.*;
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));
	 boolean[] prime = new boolean[1000001];
	 int devide =0;

	 for(int i=2; i<1000001; i++) {
		 devide = 1000000/i;
		 for(int j=2; j<=devide; j++) {
			 prime[i*j] = true;

		 }
	 }
	 prime[0] = true;
	 prime[1] = true;
//0과 1은 특별히 구분
	 int M = Integer.parseInt(br.readLine());
	 int N = Integer.parseInt(br.readLine());

	 for(int i=M; i<=N; i++) {
		 if(prime[i]==false) {
			 bw.write(i+"\n");
//false인 값을 만날 때마다 해당 index를 출력한다
		 }
	 }
	 bw.flush();
	 bw.close();
}
}


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));
	 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	 boolean[] prime = new boolean[1000001];
	 int M, N;
	 int devide =0;
//소수 배열 만들기, 반복문에서 사용되는 변수 미리 만들기
	 for(int i=2; i<1000001; i++) {
		 devide = 1000000/i;
		 for(int j=2; j<=devide; j++) {
			 prime[i*j] = true;
//false로 남은 애들만 소수가 된다
		 }
	 }
	 prime[0] = true;
	 prime[1] = true;
//0과 1은 특별히 구분
	 StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	 M = Integer.parseInt(st.nextToken());
	 N = Integer.parseInt(st.nextToken());
	 for(int i=M; i<=N; i++) {
		 if(prime[i]==false) {
			 bw.write(i+"\n");
		 }
//false인 값을 만날 때마다 해당 index를 출력한다
	 }
	 bw.flush();
	 bw.close();
}
}