第一种模拟O（n^2）
#include <iostream> #include <stdio.h> #include <math.h> #include <cstring> using namespace std; int a[105]; int main() { int n, sum, i, k, jail; scanf("%d",&n); while (n--){ scanf("%d",&jail); memset(a,0,sizeof(a)); k = 0; sum = 0; while (k <= jail){ for (i = k+1; i <= jail; i+=(k+1)){ a[i]= !a[i];//printf("%d\n",i); } ++k; // printf("%d\n",k); } for (i = 1; i <= jail; i++){ if (a[i]) sum++; } printf("%d\n",sum); } return 0; }
第二种计算1-n个数有多少个奇个数约数
#include <stdio.h> int main() { short unsigned cell[101] = {0,1,1,1,2,2},i = 0,j,top,sum = 0; int N,n; for(i = 6;i <= 100;i++) { sum = 0; top = i>>1; for(j = 2;j <= top ;j++) !(i % j) ? sum++ :0; cell[i] = cell[i-1] + sum%2; } scanf("%d",&N); while(N--) { scanf("%d",&n); printf("%d\n",cell[n]); } return 0; }
