给出一个整数集，其中包含1-n的所有整数，要求挑选出一个元素最多的子集，使得子集中任意两数的乘积不是完全平方数 (n<=10^6)
求这样一个最大子集的元素个数

#include <cstdio>

#include <cstring>

#include <cmath>

const int N = 1000006;

int b[N];

int cnt[N];

int s[N];

void init()

{

    int i, j;

    memset(b, 1, sizeof(b));

    for (i = 2; i < N; i++) {

        if (b[i]) {

            cnt[i] = i;

            for (j = i + i; j < N; j += i) {

                if(b[j]) {

                    cnt[j] = i;

                    b[j] = 0;

                } else

                    cnt[j] *= i;

            }

        }

    }

}

//法1.将范围内所有因数分解质因数，将所有含有因子不是一次的数删去

int main(int argc, char* argv[])

{

    int n, i, t;

    init();

    s[1] = 1;

    for (i = 2; i < N; i++)

    {

        if (cnt[i] == i)

            s[i] = s[i - 1] + 1;

        else

            s[i] = s[i - 1];

    }

    scanf("%d", &t);

    while (t--)

    {

        scanf("%d", &n);

        printf("%d\n", s[n]);

    }

    return 0;

}

//法2.将范围内完全平方数和完全平方数的倍数删掉

int main()

{

    int i, j;

    memset(b, 0, sizeof(b));

    for (i = 4; i < N; i++)

    {

        int sq = sqrt((double)i);

        //printf("sq = %d i = %d\n", sq, i);

        if (sq * sq == i)

            for (j = i; j < N; j += i)

                b[j] = 1;

    }

    int t, n;

    scanf("%d", &t);

    while (t--)

    {

        scanf("%d", &n);

        int ans = n;

        for (int i = 0; i <= n; i++)

            ans -= b[i];

        printf("%d\n", ans);

    }

    return 0;

}