[알고리즘] P1456. 거의 소수

 

게시물은 엄청 오랜만에 올리는 것 같은데..ㅎㅎ

백준 풀면서 에러가 어떤 에러인지 잘 읽어보라는 교훈을 얻게 되어서 오랜만에 게시글을 쓰게 되었다.

 

계속 오류 나는데 왜 오류가 나는지도 모르고 계속 코드만 보고 있었음

 

일단 거의 소수 문제부터 설명해보겠다

 

문제 링크

1456번: 거의 소수

 

문제

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

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

 

입력

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

 

출력

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

 

제한

1 ≤ A ≤ B ≤ 1014

 

일단 여기서 어떤 수가 소수의 N제곱(N>=2) 꼴일 때 그걸 거의 소수라고 하는데 A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력하라는 문제이다.

 

여기서 중요한 점 2개는 일단 첫번째로 A와 B의 범위가 10^14 보다 작거나 같을 수 있기 때문에 long형을 사용해야하며,

 

그 어떤 수의 제곱 꼴을 찾을 때 소수들 중에서 제곱 세제곱 네제곱꼴 등을 저장할 때 그것과 B를 비교하게 되면 ,,

 

즉, N^k 와 B를 비교하게 되면 LONG 형 범위를 초과할 수도 있기 때문에

 

그 둘의 비교 대신에 N과 B/(N^(k-1)) 을 비교하는 걸로 바꿔서 계산하는 게 중요한 점인 것 같다..

 

사실 소수 구하는 건 에라토스테네스의 체 구하면서 구하면 되고 그것들의 제곱한 수, 세제곱, 네제곱 계속 해가면서

 

그 B보다 작은 수 코드로 잘 비교하면 되는거라 코드 자체는 어렵지는 않았던 것 같은데

 

계속 런타임 에러가 났다..

 

 

다음부터 꼭 에러가 나면 ()안에 왜 오류가 떴는지 읽어보길...

 

처음에는 런타임 오류라는 글자만 보고 왜 그러지? 아 소수 구할 때 모든 범위 안 구해도 되고 그 제곱근까지만 구해보면 되는데(에라토스테네스의 체) 그 부분 때문에 오류가 났나? 고민을 또 하다가

 

계속 오류 나길래 포기할까 했는데 엄청 어이없는 실수였음

 

long A = Long.parseLong(st.nextToken());

long 형을 받으려면 Long.parseLong으로 받아야 하는데...

 

계속 long A = Integer.parseInt(st.nextToken()); 이렇게 받으려고 하니까 오류가 나지 바보야

 

근데 심지어 런타임 에러(NumberFormat) 이렇게 자세하게 왜 오류가 났는지도 알려줬는데 이것도 안보고 내 코드만 보고 왜 오류나는지 탐색하고 있으니까 바보지

 

나중에 런타임 에러 날 때는 왜 오류나는지 꼭 확인하고 보라는 뜻에서 이렇게 게시글까지 작성하게 되었다.ㅎㅎ

 

코드

/*240324 P1456 거의 소수*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*범위 넘어가는 거 조심..!!*/
/*LONG 범위 넘어갈까봐 일부러 N^k 승이랑 B 비교 대신 */
/*N이랑 B/(N^(k-1)) 비교하는 걸로 바꿨음*/
/*어렵긴한데 이 문제에서 제곱근 이상이려면 이미 소수가 아니라고 걸러진 수들이니까 그 이후로 진행할 필요가 없었음*/
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        /*멍청이 long이라고 했으면서 integer로 받아서 계속 오류나는거였네*/
        long A = Long.parseLong(st.nextToken());
        long B  = Long.parseLong(st.nextToken());

        long[] array = new long[10000001]; // 10^14 승이길래 그거 제곱근 10^7까지반복 //왜냐면 그게 최대니까

        for(int i = 2; i<array.length; i++) {
        	array[i] = i;
        }
        for (int i = 2; i <=Math.sqrt(array.length); i++) { // 설마.... 여기 부분 때문에 런타임 나는건가..?
			if(array[i] == 0) {
				continue;
			}
			for(int j = i+i; j<array.length; j = j+i) {
				array[j] = 0;
			}
			
		}

        int count = 0;
        for(int i = 2; i < 10000001; i++) {
        	if (array[i] != 0) {
        		long t = array[i];
        		while((double)array[i] <= (double)B/(double)t) {
        			if((double)array[i] >= (double)A/(double)t) {
        				count++;
        			}
        			t = t * array[i];
        		}
        	}
        }

        System.out.println(count); 
    }
}