풀이
제곱 ㄴㄴ 수를 직접 세어주려면 시간이 너무 오래 걸린다.
제곱 ㄴㄴ 수를 제외한 나머지는 모두 제곱 ㅇㅇ 수(?)이므로
제곱 ㅇㅇ 수(?)를 카운팅해서 전체 개수에서 빼주자!
룰루랄라
코드
#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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이