코드 복사/붙여넣기 하는 당신이 아름답습니다.

1016 : 제곱 ㄴㄴ 수

풀이

제곱 ㄴㄴ 수를 직접 세어주려면 시간이 너무 오래 걸린다.

제곱 ㄴㄴ 수를 제외한 나머지는 모두 제곱 ㅇㅇ 수(?)이므로

제곱 ㅇㅇ 수(?)를 카운팅해서 전체 개수에서 빼주자!

룰루랄라

코드

#include <stdio.h>
typedef long long ll;

bool chk[1000001], aux[1000001];

int main() {
	ll a, b;
	scanf("%lld %lld", &a, &b);
	
	int ans = b - a + 1;
	for (ll i = 2; i*i <= b; i++) {
		if (aux[i]) continue;
		for (ll j = i; j*j <= b; j += i) aux[j] = 1;
		for (ll j = ((a-1)/(i*i)+1)*i*i; j <= b; j += i*i)
			if (!chk[j - a]) chk[j - a] = 1, ans--;
	}
	
	printf("%d", ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-09-20 14:33

Read more posts by this author