[JAVA 순환 알고리즘] 백준 알고리즘 1456번 / 거의소수 찾기

package baekjoon;
 
import java.util.Scanner;
import java.util.Vector;
/**
 * 
 * 백준 알고리즘 거의소수 찾기 문제
 * @Package : baekjoon
 * @FileName : baek1456.java
 * @Author : Yang TaeIl
 * @date : 2018. 2. 27. 
 *
 */
class primeNumFind {
    long max;
    long min;
    boolean[] IsNotPrime;
    int[] primeNum;
    //Vector<Integer> a = new Vector<Integer>();
 
    primeNumFind(long min, long max) {
        this.max = max;
        this.min = min;
    }
 
    void find() {
        int cntPrime=0;
        primeNum=new int[10000001];
        IsNotPrime = new boolean[10000001];
        for (int i = 2; i <10000001; i++) {
 
            if (IsNotPrime[i]) {
                i++;
                continue;
            } else {
                primeNum[cntPrime++]=i;
                //a.add(i);
                for (int j = 2; j <= 10000000; j++) {
                    if (i * j >= 10000000)
                        break;
                    IsNotPrime[i * j] = true;
                }
                if (i != 2)
                    i++;
            }
 
        }
        //System.out.println(cntPrime);
        int cnt = 0;
        long TMax = 1000000000000000L;
        for (int k : primeNum) {
            if(k==0)break;
            long n = k;
            while (k <= max / n) {
                if (k * n >= min)
                    cnt++;
                n = n * k;
            }
        }
        System.out.println(cnt);
    }
 
}
 
public class baek1456 {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long m = sc.nextLong();
        long n = sc.nextLong();
        primeNumFind a = new primeNumFind(m, n);
        a.find();
    }
 
}
 

백준에서 임의로 정의한 거의소수라는 수를 찾는 문제였습니다.

입력을 1~ 10^14 까지 받을 수 있습니다.

이 문제의 핵심은 시간줄이기였습니다.

소수를 구할 때 1부터 자기자신만으로 나누어진다는 정의를 사용해서 구하다보면 시간복잡도는 O(n)이됩니다.

n개의 숫자를 구하다보면 O(n^2)이 되겠지요. 하지만 조금 더 생각해보면 n의 숫자가 소수인지 판별할때 굳이 n까지가아니라 n^1/2만큼만 검사하면 된다는 것을 알 수 있습니다. 이렇게 되면 시간복잡도는 다시 n이 되겠지요.

그러나 10^14라는 어마어마하게 큰수를 하다보면 연산속도가 느려지는 것은 어쩔 수 없었습니다.

따라서 소수를 미리 구해서 곱해서 구하자는 생각을 해보았습니다. 이 과정에서 소수를 대량으로 구하려면 boolean배열을 선언해서 2부터 시작해서 배수들은 소수가 아니므로 isNotPrime를 true로 변경하고,  다음에 false인 수를 만나면 그 수는 소수라는 것을 생각해 내었습니다. 이 방법으로 빠른 속도로 소수를 구했고, 범위 안의 소수의 제곱 수를  모두 세는 것으로 문제를 풀 수 있었습니다.