题目大意：判断2到m有多少个数字是合法的。

对于给定的n个数，是合法的；其他数字若是合法，那么必须存在2到n-1的约数，且这些约数都是合法的。

暴力求解：从小到大枚举2到m，如果约数都合法，标记该数字合法；如果遇到一个不合法的约数，则不标记合法。

需要从小到大确定是否合法，保证用到的约数都是更小的、已确定是否合法。时间复杂度：

#include <stdio.h>
#include <string.h>
#define N 300005
int t, n, m, i, j, k, ans, f[N];
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        memset(f, ans=0, sizeof(f));
        for(i=1; i<=n; i++){
            scanf("%d", &k);
            f[k] = 1;
        }
        for(i=2; i<=m; i++){
            if(f[i]) ans++;
            else{
                for(k=0, j=2; j*j<=i; j++){
                    if(i%j) continue;
                    k = 1;
                    if(!f[j] || !f[i/j]) break;
                }
                if(k && j*j > i) ans++, f[i] = 1;
            }//有约数且约数都合法
        }
        printf("%d\n", ans);
    }
    return 0;
}

筛选法求素数：用筛法预处理出每个数字的约数个数（被筛掉次数），保存到数组c，如c[i]表示i的约数个数（2到n-1），如果是质数，约数设为无穷大。

题目要求，所有约数都是合法的；那我们就用合法的数字对2到m的数字进行筛选法求素数；如果“约数”个数恰好根c一致，那么全部约数都是合法的。（质数永不合法，除非属于集合S）。

时间复杂度：

#include <stdio.h>
#include <string.h>
#define N 300005
int t, n, m, i, j, k, ans, c[N], f[N];
int main(){
    for(i=2; i<N; i++){
        if(c[i] == 0) c[i] = N;//质数无真因子
        for(j=i+i; j<N; j+=i) c[j]++;
    }//统计约数个数
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        memcpy(f, c, sizeof(f));
        for(i=1; i<=n; i++){
            scanf("%d", &k);
            ans = f[k] = 0;//约数被筛完合法
        }
        for(i=2; i<=m; i++){
            if(f[i] > 0) continue;//不合法
            ans++;
            for(j=i+i; j<=m; j+=i) f[j]--;
        }//合法的数能被合法的数筛完
        printf("%d\n", ans);
    }
    return 0;
}