[알고리즘] 1456번

오늘 풀어볼 문제는 백준 1456번 문제 "거의 소수" 이다.

이 문제는 골드5 문제이고 정수론 문제이다.

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

📌첫 번째 도전📌
앞에서 푼 문제처럼 배열에 소수인 값들을 넣어준다. 그 후 for문을 통해 Max와 Min 사이에 존재하는 소수가 있다면 count를 증가시킨다.

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

        long Min = sc.nextLong();
        long Max = sc.nextLong();
        long[] arr = new long[10000001];

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

        for(int i = 2; i <= Math.sqrt(arr.length); i++) {
            if(arr[i] == 0) {
                continue;
            }
            for(int j = i + i; j < arr.length; j = j + i) {
                arr[j] = 0;
            }
        }

        int count = 0;
        for(int i=2; i < 10000001; i++) {
            if(arr[i] != 0) {
                long temp = arr[i];

                while((double)arr[i] <= (double)Max/(double)temp) {
                    if((double)arr[i] >= (double)Min/(double)temp) {
                        count++;
                    }
                    temp = temp * arr[i];
                }
            }
        }
        System.out.println(count);
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1456