给定一个区间 [n,m]，求有多少个数不含平方因子。

首先  求出不超过m的所有素数p，用p^2筛掉 [n,m] 之间的所有倍数。

int Euler(int n) {    memset(vis,0,sizeof(vis));    int phi = 0;    for(int i=2;i<=n;i++) {        if(!vis[i]) prime[phi++] = i;        for(int j=0;j
     
      <=n;j++) {            vis[i*prime[j]] = 1;            if(i%prime[j]==0) break;        }    }    return phi;}
     

 

欧拉公式求出素数表。

用素数的p^2筛选。

bool squre[maxn]; //筛去[n,m] 中的平方因子数 squre[i-n] = 1 筛去。int Eratosthenes(int n,int m) {    memset(squre,0,sizeof(squre));    for(int i=0;prime[i]*prime[i]<=m;i++) {        int d = prime[i]*prime[i];        for(int j=1;d*j<=m;j++)            if(j*d>=n)                squre[j*d-n] = 1;    }    int ans = 0;    for(int i=0;i<=m-m;i++) {        if(!squre[i])            ans++;    }    return ans;}