[Algorithm/C] BOJ.1016 제곱ㄴㄴ수(미해결)

나의 첫번째 시도

1. min 부터 max 까지 모든 숫자중에 제곱수를 빼준다.

/*

https://www.acmicpc.net/problem/1016

제곱ㄴㄴ수

M과 N이 주어질 때 M이상 N이하의 자연수 중 

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 

제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, 

min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

Writer : Mun Jae In

Date : 2017.12.25

*/

#include <stdio.h>

#include <math.h>

int main(int argc, char * argv[])

{

int min;

long long max;

int cnt=0;

int i;

scanf("%d %lld", &min, &max);

for(i=min,cnt=(int)(max-min)+1; i<=max; i++)

{

if(sqrt((double)i)-(int)sqrt((double)i) == 0)

cnt--;

}

printf("%d",cnt);

}

이렇게 제출하면 틀렸다고 나온다. 아마도 min 과 max 를 다 탐색하려면 시간이 너무 오래걸려서 그런것 같다.

/*

https://www.acmicpc.net/problem/1016

제곱ㄴㄴ수

M과 N이 주어질 때 M이상 N이하의 자연수 중 

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 

제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, 

min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

Writer : Mun Jae In

Date : 2017.12.25

*/

#include <stdio.h>

#include <math.h>

int main(int argc, char * argv[])

{

int min;

long long max;

long long cnt=0;

scanf("%d %lld", &min, &max);

if(min>1 && max<=1000000000000 && max-min<=1000000)

{

printf("%lld\n",(max-min+1)-(int)sqrt((long double)max)+(int)sqrt((double)min));

}

if(min==1 && max<=1000000000000 && max-min<=1000000)

{

printf("%lld\n",(max-min+1)-(int)sqrt((long double)max));

}

}

반복문을 사용하지 않고 풀었는데도 틀렸다.... 왜 틀렸지?

제곱수의 배수도 제곱수로 나누어 떨어지기 때문에 틀렸다.

출처