BOJ 1016 제곱 ㄴㄴ 수

문제에서 어떤 두 정수 min과 max 사이에 수가 1보다 큰 제곱수로 나누어 떨어지지 않을때 제곱 ㄴㄴ 수 라고 정의를 하였다. 어떤 수가 제곱수로  나누어 떨어지지 않은것을 구하기 위해 우리는 에라토스테네스 방법을 응용할 수 있다.

 

처음 떠올린 방법은 부르트포스로 생각하였는데 제곱수가 될수 있는 n이 1000000, max-min이 1000000이므로 1000000*1000000 즉 1조가되어 시간초과가 발생한다.

 

기본적인 에라토스테네스는 소수를 구하기 위해 2,3,5,7의 배수를 모두 지우고 지워지지 않고 남은 수를 우리는 소수임을 알수 있다.

 

이를 응용하여 i*i (i>1) 가 max 보다 작을때 까지 i*i의 배수를 모두 지워주면 된다. 이때 시작지점은 i*i 가 min 보다는 커야하므로 min/(i*i)을 기준으로 계산하면 된다. 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

long long arr[1000002];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	memset(arr, 0, sizeof(arr));

	long long small, large;
	cin >> small >> large;

	long long cnt = 0;
	long long i = 2;

	while(i*i <= large){
		long long sNum = small / (i*i);
		if(small % (i * i) != 0)
		{
			sNum += 1;
		}
		while(i*i*sNum <= large)
		{
			arr[i*i*sNum - small] = 1;
			sNum++;
		}
		i++;
	}
	
	for(long long i = 0; i <= 1000002; i++)
	{
		if(arr[i] == 1)
		{
			cnt++;
		}
	}

	cout << large - small +1 - cnt;
}

 풀이는 다음과 같다. 시작 인덱스는 sNum으로 small이 min, large가 max에 해당된다.

long long sNum = small / (i*i);를 이용하여 시작 인덱스를 구하고 만약 min이 제곱수로 나누어지지 않는다면 시작 인덱스를 하나 증가시켜준다. 이후 (i*i)*sNum이 large 보다 작다면 sNum을 증가시켜 반복한다. 

 

마지막으로 제곱수의 배수를 arr에 표시해주고 최종적으로 arr에 1의 갯수를 구한후 전체에서 빼주면 된다.