[백준 알고리즘] 1016번 제곱 ㄴㄴ수 c++

소수를 구하는 에스토스테네스의 체를 기반으로 한 알고리즘 풀이이다.

list에 min-max의 최대인 1000001을 할당한다.

2부터 제곱이 max보다 작거나 같을 때까지

모든 수의 제곱의 배수를 탐색한다.

제곱의 배수의 시작점은 값이 min보다 크거나 같을때이다.

따라서 x=min/i*i로 배수의 시작점을 구할 수 있고,

i의제곱이 min일 확인하기 위해 min%(i*i)=0이면 x를 1감소한다.

list에서 제곱의 배수가 되는 위치는 true로 저장하여

list에서 false인 경우에 제곱 ㄴㄴ수이므로 해당 값을 카운트하여 출력한다.

 

#include <iostream>
#include <vector>

using ll = long long;

using namespace std;

bool list[1000001];

int main(){

	ll min, max;
	

	cin >> min >> max;

	ll cnt = 0;



	for(ll i=2; i*i<=max; i++){
		ll x = (min/(i*i));
		
		if(min%(i*i)==0){
			x--;
		}

		for(ll j=i*i*(x+1); j<=max; j+=i*i){
			list[j-min] = true;
		}
	}

	for(int i=0; i<=max-min; i++){
		if(list[i] == 0){
			cnt ++;
		}
	}

	cout << cnt << endl;

	return 0;
}