http://acm.hdu.edu.cn/showproblem.php?pid=1286
题意：输入T 有T组
每组输入n 问1~n之间有多少个跟n有大于公约数的数。
思路：找n的约数m，然后把m的所有小于n的倍数都找出来a[m]=1
#include<stdio.h> #include<string.h> #define M 32777 int a[M]; int main() { int n,m,sum,i,j; scanf("%d",&n); while(n--) { scanf("%d",&m); memset(a,0,sizeof(a)); for(i=2;i<=m/2;i++) { if(m%i==0) { for(j=i;j<m;j+=i) a[j]=1; } } sum=0; for(i=2;i<m;i++) if(a[i]) sum++; printf("%d\n",m-sum-1); } return 0; }
原文：https://www.cnblogs.com/Kohinur/p/8893686.html