BOJ 백준온라인져지 1456 거의 소수 풀이

1^14 의 square root 는 1^7이다.

1^7까지의 소수만 구해주면 된다.

그래서 2~1^7까지의 소수를 구하고, 

	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/1456
	* BOJ 백준온라인져지 1456 거의 소수 풀이
	*/
	int main(){
	long long min, max;
	int count = 0;
	scanf("%lld%lld", &min, &max);
	bool *isPrimeNumber = new bool[(int)1e+7 + 1];
	int *primeNumber = new int[(int)1e+7 + 1];
	int cnt = 0;
	for(long long i = 2; i * i <= max ; i++){
	if(!isPrimeNumber[i]){
	for(long long j = i * 2; j * j <= max; j += i) isPrimeNumber[j] = true;
	primeNumber[cnt++] = i;
	}
	}
	for(int i = 0; i < cnt; i++){
	long long n = primeNumber[i];
	while(primeNumber[i] <= max / n){
	if(primeNumber[i] * n >= min) count++;
	n *= primeNumber[i];
	}
	}
	printf("%d", count);
	}

view raw BOJ_1456.cpp hosted with ❤ by GitHub

primeNumber에 소수들을 넣어준다.

primeNumber에 들어간 소수들로 

max => n * primeNumber[i]를 계산해준다.

여기서 주의해야 될 점이 n이 long long을 넘어가는 경우다.

하지만 이항을 해서

max / n >= primeNumber[i]로 변경할 수 있다.

그리고 min >=의 경우를 구해야줘야 되는데, 이미 while loop에서 체크를 해줘서 밑에서는 체크를 안해줘도 된다.