거의 소수 1456

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

10^14 까지 입력을 받는다고 한다. 엄청 큰수이다. 이거를 줄일방법을 먼저 생각하였다
어떤 소수 N의 거의소수중 가장 작은수는 N^2 이다. 거의소수는 10^14을 넘지 않아야 한다.
즉 10^7 까지만 소수를 찾으면된다. 그이상의 소수로 거의소수를 만들면 10^14를 넘어서니까

그래서 2부터 10^7 까지 반복문 돌면서 거의 소수 C 를 만들고 C가 A~B 사이에 있는지 확인하는 방식으로 코드를 만들었다

결과는 시간초과가 났다
소수인지 매번 확인하는 부분때문이다
시간초과를 줄일 방법이 떠오르지 않았다. 그래서 검색을 한결과 소수를 10^7 까지 에라토스테네스의 체 알고리즘을 사용해서 구하면 된단다.

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        long A = Long.parseLong(input[0]);
        long B = Long.parseLong(input[1]);

        long len = (long)Math.sqrt(B);

        long answer = 0;
        for (long i = 2; i <= len; i++) {
            if(isPrime(i)){

                long mul = 2;
                long next = (long)Math.pow(i, mul);
                while(next <= B){
                    if(next >= A){
                        answer++;
                    }
                    mul++;
                    next = (long)Math.pow(i, mul);
                }

            }
        }

        System.out.println(answer);
    }
    public static boolean isPrime(long num){
        if(num == 0 || num == 1)
            return false;

        for(long i = 2; i <= Math.sqrt(num); ++i){
            if(0 == num%i){
                return false;
            }
        }

        return true;
    }
}

for문을 두번 10^7 x 10^7 만큼 돌린다고 생각하니 이게 말이되나 싶은데 실제로 시간복잡도는
O(n log log n)이란다.. 약 8450980 의 값이다. 이거 모르면 이문제는 못풀지 싶다...

for (int i = 2; i * i <= len; i++) {
            if (primes[i]) {
                for (int j = i * i; j <= len; j += i) {
                    primes[j] = false;
                }
            }
        }

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        long A = Long.parseLong(input[0]);
        long B = Long.parseLong(input[1]);

        int len = (int)Math.sqrt(B);

        boolean[] primes = new boolean[len+1];
        Arrays.fill(primes, true);
        primes[0] = primes[1] = false;

        for (int i = 2; i * i <= len; i++) {
            if (primes[i]) {
                for (int j = i * i; j <= len; j += i) {
                    primes[j] = false;
                }
            }
        }

        int answer = 0;
        for (int i = 2; i <= len; i++) {
            if(primes[i]){
                int mul = 2;
                long next = (long)Math.pow(i, mul);
                while(next <= B){
                    if(next >= A){
                        answer++;
                    }
                    mul++;
                    next = (long)Math.pow(i, mul);
                }
            }
        }

        System.out.println(answer);
    }
    public static boolean isPrime(long num){
        if(num == 0 || num == 1)
            return false;

        for(long i = 2; i <= Math.sqrt(num); ++i){
            if(0 == num%i){
                return false;
            }
        }

        return true;
    }
}

이 코드는 에라토스테네스의 체 알고리즘의 일부입니다. 이 알고리즘의
목적은 주어진 범위 내의 모든 소수를 찾아내는 것입니다.

프로그램이 동작하는 방식은 다음과 같습니다:

    i를 2부터 sqrt(len)까지 증가시키며 반복문을 실행합니다.
    만약 i가 소수라면, i의 배수를 모두 소수가 아닌 것으로 표시합니다.
    이를 위해 j를 i * i부터 시작하여 len까지 i만큼씩 증가시키며
    반복문을 실행하고, 이 j들을 모두 소수가 아닌 것으로 표시합니다.

따라서, j = i * i; j <= len; j += i 코드의 의미는 "소수 i의
배수들을 모두 소수가 아닌 것으로 표시한다"입니다.

이 방식을 사용하는 이유는, i 이전의 모든 소수의 배수는 이미 이전
단계에서 처리되었기 때문입니다. 예를 들어, i가 3일 때, 3 * 2는
이미 i가 2일 때 처리되었습니다. 따라서 i * i부터 처리를 시작하는 것입니다.