数学--数论--HDU 2582 F(N) 暴力打表找规律

#include <iostream>
#include<cstdio>
#define ll long long
#define maxn 1000000
using namespace std;
int zs[maxn], t = 0, n;
ll f[maxn + 5];
bool v[maxn + 5];

int main()
{
    for (int i = 2; i <= maxn; i++)
    {
        if (!v[i]) f[i] = zs[++t] = i;
        for (int j = 1,u = zs[j] * i;  j <= t && u<= maxn; j++)
        {
            v[u] = 1;
            if (!(i % zs[j]))
            {
                f[u] = f[i];
                break;
            }
            f[u] = 1;
            u = zs[j+1] * i; 
        }
    }
    for (int i = 4; i <= maxn; i++)
        f[i] += f[i - 1];
    while (scanf("%d", &n)!=EOF)
        printf("%lld\n", f[n]);
    return 0;
}