038 : 거의 소수 구하기

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        // Input Supply Cable
        Scanner sc = new Scanner(System.in);
        long Min = sc.nextLong();
        long Max = sc.nextLong();

        // Preprocessing
        long[] A = new long[10000001];
        for (int i = 2; i < A.length; i++) {
            A[i] = i;
        }

        // Operating Sieve(1/2)
        for (int i = 2; i <= Math.sqrt(A.length); i++) {
            if (A[i] == 0) {
                continue;
            }
            for (int j = i + i; j < A.length; j = j + i) {
                A[j] = 0;
            }
        }
        
        // Operating Counter(2/2)
        int count = 0;
        for (int i = 2; i < 10000001; i++) { 
            if (A[i] != 0) {
                long temp = A[i];
                while ((double)A[i] <= (double)Max / (double)temp) {
                    if ((double)A[i] >= (double)Min / (double)temp) {
                    count++;
                    }
                    temp = temp*A[i];
                }
            }
        }

        // Output Extracting Cable
        System.out.println(count);

    }
}

 

소수 정보를 F[i]로 공급한다 (phaser로  사용)

 

for문으로 linear 작업 공간 X (phaser를 통과하는) X while문 

 

while문의 squeezer

- temp를 늘여 MAX를 작게 만든다 or

- F[i]*temp 가 커지는

 

while X if 내부에 있을 때만 counter++;

receiver patch 부착

OEC 해야 하므로 for문 바깥에서 counter를 만든다