[백준] 1929번: 소수 구하기

 

 

 

제목: 소수 구하기

실버3

 

---

문제

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

입력

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

출력

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

---

예제 입력 1 복사

3
5
7
11
13

예제 출력 1 복사

3 16

---

 

 

 

🔑 코드

---

 

case1:

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());
			primeNumber(M, N);
			
		}
	
		static void primeNumber(int M, int N) {
			//에라토스테네스의 체 이용
			boolean[] b = new boolean [N+1];
			b[0]=true;
			b[1]=true;
			
			for(int i=2;i*i<b.length;i++) {
				for(int j=i*i;j<=N;j+=i) {
					if(!b[j]) {
						b[j]=true;
					}
				}
			}
			for(int i=M;i<b.length;i++) {
				if(!b[i]) System.out.println(i);
			}
		}
}

 

 

 

case2:

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());
		boolean[] bArr = new boolean[N + 1];
		primeNumber(M, N, bArr);

		for (int i = M; i <= N; i++) {
			if (!bArr[i])
				System.out.println(i);
		}
	}

	static void primeNumber(int M, int N, boolean[] bArr) {
		// 에라토스테네스의 체 이용
		bArr[0] = true;
		bArr[1] = true;

		for (int i = 2; i < Math.sqrt(bArr.length); i++) {
			if (bArr[i])
				continue;
			for (int j = i * i; j <= N; j += i) {
				if (!bArr[j]) {
					bArr[j] = true;
				}
			}
		}
	}
}

 

case3(StringBuilder 사용):

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());
		boolean[] bArr = new boolean[N + 1];
		primeNumber(M, N, bArr);

		StringBuilder sb = new StringBuilder();
		for (int i = M; i <= N; i++) {
			if (!bArr[i])
				sb.append(i).append('\n');
		}
		System.out.println(sb);
	}

	static void primeNumber(int M, int N, boolean[] bArr) {
		// 에라토스테네스의 체 이용
		bArr[0] = true;
		bArr[1] = true;

		for (int i = 2; i < Math.sqrt(bArr.length); i++) {
			if (bArr[i])
				continue;
			for (int j = i * i; j <= N; j += i) {
				bArr[j] = true;
			}
		}
	}
}

 

---

 

 

 

 

 

알고리즘 분류

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

 

 

 

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

 

 

 

커버사진

<a href="https://www.flaticon.com/kr/free-icons/" title="연산 아이콘">연산 아이콘  제작자: Flat Icons - Flaticon</a>

https://www.flaticon.com/kr/free-icon/algorithms_1753819