[java]백준 1456번: 거의 소수, prime number 소수, 제곱근 Math.sqrt(N), 아리토스테네스의 체 원리, 제곱 Math.pow(a,b)

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

1456번: 거의 소수

 

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

 

소수 구하기의 핵심 이론

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

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

 

---

 

코드

 

import java.util.Scanner;

public class j1456 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextInt();
		long B = sc.nextInt();

		// 소수를 B의 제곱근까지 구하기
		// 거의소수의 크기는 해당 소수의 제곱부터이므로 B의 제곱근까
		int length = (int) Math.sqrt(B) + 1;

		// 아리토스테네스의 체 원

		// 1. 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성한다.
		long[] prime = new long[length];

		for (int i = 2; i < length; i++) {
			prime[i] = i;
		}

		int result = 0; // 답

		// 2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때
		// 처음으로 선택된 숫자는 지우지 않는다.
		// 지운 숫자는 0으로 표시했다.
		for (int i = 2; i < length; i++) {
			if (prime[i] == 0) { // 지운 숫자이면 다음으로 넘어감
				continue;
			}
			result += Square(i, A, B); // 소수의 N제곱인 거의 소수의 개수 더해줌(A~B)
			for (int j = i + i; j < length; j = j + i) { // 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지운다.
				prime[j] = 0;
			}
		}

		System.out.println(result);

	}

	static int Square(int num, long a, long b) {
		// 거의 소수 개수 구하기
		int cnt = 0; // 개수
		int N = 2; // N제곱 (N >=2)
		while (Math.pow(num, N) <= b) { // Math.pow(a,b) a의 b제곱, b보다 작으면 계속 더 큰 제곱 구해준다
			if (Math.pow(num, N) >= a) { // a보다 클 때 개수 ++
				cnt++;
			}
			N++;
		}

		return cnt;
	}
}

 

풀이

1. 소수는 에라토스테네스의 체 사용해서 구함 -> 에라토스테네스의 원리는 아래 게시물에서 확인 
2. 소수를 구할 때 범위는 B의 제곱근까지 → 소수의 제곱부터가 거의소수이기 때문에  (근데 귀찮아서 제곱근까지 안했는데 돌아감 ㅋ 하지만 시간복잡도를 생각해서 제곱근까지 구하고 아래에서 구하는게 정석)
3. 메소드 Square 사용하여 해당 범위의 거의 소수 개수 구함. 해당 소수의 N제곱 

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

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

 

Math.pow(a,b)
a의 b제곱

 

 

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