[java]백준 1929번- 소수 구하기, prime number 소수, 제곱근 Math.sqrt(N), 아리토스테네스의 체 원리

 

1929번: 소수 구하기

 

 

소수prime nuber
자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수
1과 자기 자신 외에 약수가 존재하지 않는 수

 

소수 구하기의 핵심 이론

에라토스테네스의 체 원리
① 구하고자 하는 소수의 범위만큼 1차원 배열을 생성
② 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움. 이때 처음으로 선택된 숫자는 지우지 않음
③ 배열의 끝까지 ②를 반복한 후 배열에서 남아 있는 모든 수를 출력

-> 에라토스테네스의 체를 사용할 때 시간 복잡도는?
일반적으로 에타토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있습니다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))입니다. 그 이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문입니다. 이러한 이유  때문에 에라토스테네스의 체 기법은 현재에도 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용되고 있습니다.

 

---

코드

 

import java.io.*;
import java.util.*;

public class j1929 {
	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()); // M 이상
		int N = Integer.parseInt(st.nextToken()); // N 이하

		// 에라토스네스의 체 원리
		// 1. 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성합니다.
		int[] A = new int[N + 1];
		for (int i = 2; i <= N; i++) {
			A[i] = i;
		}

		// 2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때
		// 처음으로 선택한 숫자는 지우지 않습니다.

		for (int i = 2; i < Math.sqrt(N) + 1; i++) {
			if (A[i] == 0) {//지운 숫자는 탐색하지 않는다.
				continue;
			}
			for (int j = i + i; j <= N; j = j + i) {
				//선택한 숫자의 배수면 지운다. 0으로 바꿔줌
				A[j] = 0;
			}
		}

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

	}
}

 

풀이

팁!!!!!!!!!!N의 제곱근까지 탐색한다.

 

아래 발행글에 들어가면 제곱근까지 탐색하는 이유 있음!!!

 

2021.03.14 - [알고리즘/파이썬 알고리즘] - 파이썬 자료구조와 알고리즘_소수

파이썬 자료구조와 알고리즘_소수

 

 

제곱근
Math.sqrt(N)

 

 

 

에라토스테네스의 체 원리를 사용하여

① 구하고자 하는 소수의 범위만큼 1차원 배열을 생성

// 에라토스네스의 체 원리
		// 1. 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성합니다.
		int[] A = new int[N + 1];
		for (int i = 2; i <= N; i++) {
			A[i] = i;
		}

 

 

② 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움. 이때 처음으로 선택된 숫자는 지우지 않음

***************** 배수를 지워주기 위하여 첫번째 for문에서 탐색할 때 제곱근까지 탐색해준다!!!

팁!!!!!!!!!!N의 제곱근까지 탐색한다.

제곱근
Math.sqrt(N)

아래 발행글에 들어가면 제곱근까지 탐색하는 이유 있음!!!

 

2021.03.14 - [알고리즘/파이썬 알고리즘] - 파이썬 자료구조와 알고리즘_소수

파이썬 자료구조와 알고리즘_소수

 

//A[j]=0으로 지운 숫자를 0으로 표시

// 범위는 j=i+i, i의 첫번째 배수부터 ~~ N까지,  j=j+i로 배수 단위로 탐색한다.

// 2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때
		// 처음으로 선택한 숫자는 지우지 않습니다.

		for (int i = 2; i < Math.sqrt(N) + 1; i++) {
			if (A[i] == 0) {//지운 숫자는 탐색하지 않는다.
				continue;
			}
			for (int j = i + i; j <= N; j = j + i) {
				//선택한 숫자의 배수면 지운다. 0으로 바꿔줌
				A[j] = 0;
			}
		}

 

 

③ 배열의 끝까지 ②를 반복한 후 배열에서 남아 있는 모든 수를 출력

// A[i]!=0.  지운 숫자 0이 아닌 숫자들이 소수이므로 M~N사이에서 출력

 

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

 

 

 

출처: 백준, Do it! 알고리즘 코딩테스트 자바 편