[백준] [c++] 1016 번 제곱ㄴㄴ수

제곱 ㄴㄴ 수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	20333	2933	1944	18.938%

문제

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

입력

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.

출력

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

​

​

​

진짜 너무 매우 아주 힘들었던 문제

 

 

#include <stdio.h>
int arr[1000001];

int main() {
	
	long long min1, max1;
	long long cnt= 0;
	scanf("%lld %lld", &min1, &max1);
	
	for (long long i = 2; i*i <= max1; i++) {
		for (long long j = ((min1 - 1) / (i*i) + 1)*i*i; j <= max1;j+=i*i) {
			arr[j-min1] = 1;
		}
	}
	for (long long i = 0; i <= max1-min1+1; i++) {
		if (arr[i]) cnt++;
	}
	printf("%lld", max1-min1 - cnt+1);
	return 0;
}