Boj1124_언더프라임
백준 1124 언더프라임
쉬운 최대공약수 + 소수 문제인듯 하였지만 많이 틀림. 가장 작은 최소공배수로 나누고 나눈 수에 대해 잘 생각해보자!
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int a, b, arr[100010], ans;
void make() {
for (int i = 2; i <= sqrt(100000); i++) {
if (arr[i]) continue;
for (int j = i*i; j <= 100000; j += i) {
if (!arr[j]) arr[j] = i;
}
}
}
int main() {
make();
scanf("%d %d", &a, &b);
for (int i = a; i <= b; i++) {
int cnt = 0, now = i;
while (arr[now] != 0) {
now /= arr[now];
cnt++;
}
if (now!=0) cnt++;
if (cnt!=0 && cnt != 1 && arr[cnt]==0)
ans++;
}
printf("%d", ans);
}