BOJ #1016 제곱ㄴㄴ수

문제

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

 

---

소스코드(C언어)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <time.h>

int iscmp[1000100] = { 0 }; //0이면 소수 1이면 합성수
long long isprime[1000100] = { 0 }; //소수^2들의 집합
int yes[1000100] = { 0 }; //0이면 yes[min+diff]는 제곱ㄴㄴ수

int main() {
	long long min, max;
	scanf("%lld %lld", &min, &max);

	isprime[0] = 4;
	int idx = 1;

	iscmp[0] = iscmp[1] = 1;
	for (long long i = 3; i <= (long long)sqrt(max); i += 2) { 
		//소수 찾기, 홀수만 검사
		if (iscmp[i] == 0) {
			//i는 소수
			isprime[idx++] = i * i;
			for (int k = i + i; k <= (long long)sqrt(max); k += i) {
				iscmp[k] = 1;
			}
		}
	}

	long long diff = max - min;
	long long num = diff + 1;
	for (int i = 0; i < idx; i++) {
		long long tmp = min / isprime[i];
		tmp = tmp * isprime[i] - min;
		if (tmp < 0)
			tmp += isprime[i];
		for (long long j = tmp; j <= diff; j += isprime[i]) {
			if (yes[j] == 0) {
				yes[j] = 1;
				num--;
			}
		}
	}
	printf("%lld\n", num);
	return 0;
}

 

Idea

소수 찾기 / 제곱ㄴㄴ수 찾기 모두 에라토스테네스의 체를 이용한다.

그래도 계속 시간초과가 떴었는데,,

그 이유인 즉슨 "소수를 찾으면, 소수의 배수들을 모두 제거한다"에서 "소수를 찾으면"을 잘못 생각했었기 때문이다.

 

소수 찾기 → 소수의 배수들을 제거하고 나면, 제거되지 않은 바로 다음 수는 소수이다.

제곱ㄴㄴ수 찾기 → min과 max사이에서 정수제곱으로 나누어 떨어지는 첫번째 수를 찾고, 그보다 큰 정수제곱의 배수들을 제거해준다. 

 

Tip

실행 시간을 측정하고 싶을 때는 <time.h>라이브러리에 있는 clock()함수를 사용한다.

clock_t형 변수(start, end)를 잡고, (end-start)/CLOCKS_PER_SEC를 float형으로 변환하여 출력해주면 실행 시간을 알 수 있다.