1456번: 거의 소수

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

#include<stdio.h>
#include<math.h>
long long int tmp, A, B, rt, ans, i, j, cnt, data[700000];
bool check[10000010];
int main()
{
    scanf("%lld%lld", &A, &B);
    rt = sqrt(B);
    for (i = 2; i <= rt; i++)
    {
        if (check[i] == true) continue;
        data[++cnt] = i;
        for (j = i * 2; j <= rt; j += i)
        {
            check[j] = true;
        }
    }
    for (i = 1; i <= cnt; i++)
    {
        tmp = B / data[i] / data[i];
        while (tmp >= 1)
        {
            ans++;
            tmp /= data[i];
        }
        tmp = (A - 1) / data[i] / data[i];
        while (tmp >= 1)
        {
            ans--;
            tmp /= data[i];
        }
    }
    printf("%lld", ans);
    return 0;
}