给定一个区间 [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<phi&&i*prime[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; }