[백준 1456] 거의 소수 (JAVA)

백준 1456번 문제  - 거의 소수

1456번: 거의 소수

---

문제 분석

 

• 거의 소수 : 소수의 N제곱 
• A부터 B까지 수 중에 거의 소수의 개수를 출력해라

---

해결 키 포인트

 

• 정수론: 소수구하기 - 에라토스테네스의 체의 원리
• 1 ≤ A ≤ B ≤ 10^14
  • int, long 타입보다 큰 수가 시작, 끝 값으로 입력될 수 있다.
  • 어차피 배열 탐색에 필요한 index 는 2 ~ B의 제곱근
    → 그러니 long타입으로 설정할 수 있는 값으로 배열의 사이즈는 10^14의 제곱근인 10^7(10000001)로 설정
• 비교할 때, num^k <= B 을 비교하기에는 num^k가 long 타입을 넘을 수 있음
  • num^(k-1) * num <= N → num <= N/num^(k-1) 로 비교

---

에라토스테네스의 체의 원리

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. ( 1도 소수가 아니다 ) 

 

에라토스테네스의 체 원리 알고리즘

 

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

2. 2부터 시작해 N의 제곱근까지 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다

3. 2~N의 제곱근 까지 탐색을 반복한 후 배열에서 남아있는 모든 수를 출력

 

N의 제곱근까지만 탐색하는 이유

N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다. 
만약 16의 범위까지 소수를 구할 때 16 = 4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게된다는 뜻
따라서 4까지만 확인하고 소수 판별을 진행하면 된다.

---

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

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

        // M, N 입력
        long M = sc.nextLong();
        long N = sc.nextLong();

        // 최대 N 값은 10^14이므로 이의 제곱근인 10^7로 배열 설정
        // (제곱근까지 값을 탐색할 것이므로)
        nums = new long[10000001];

        // 0 이상 N 이하 배열 제작
        for (long i = 0; i < 10000001; i++) {
            nums[(int) i] = i;
        }

        // 2부터 N까지 확인
        for (long i = 2; i <= Math.sqrt(10000001); i++) {
            // 해당 값이 0이 아닐 때 출력 ( 0이면 소수가 아니라 제거된 값 )
            if (nums[(int) i] != 0) {
                distinction((int) i);
            }
        }

        int count = 0;

        // 2부터 N까지 확인
        for (long i = 2; i < 10000001; i++) {
            Long num = nums[(int) i];
            //해당 값이 1보다 클 때 count 증가 ( 0이면 소수가 아니라 제거된 값 )
            if (num > 1) {
                long newNum = num;
                // num^k <= N 을 비교하기에는 num^k가 long타입을 넘을 수 있음
                // 그러므로, num^(k-1) * num <= N --> num <= N/num^(k-1) 로 비교
                while ((double) num <= (double) N / (double)newNum) {
                    if((double) num >= (double) M / (double) newNum) {
                        // 값 안에 존재하는 거의 소수일 경우 count 증가
                        count++;
                    }
                    newNum *= num;
                }
            }
        }

        System.out.println(count);
    }

    public static void distinction(int i) {
        for (long j = i+i; j < 10000001; j = j+i) {
            nums[(int) j] = 0L;
        }
    }
}