[USACO08DEC]拍头Patting Heads
本题与质数并没有什么关系，但是运用到了筛法的思想。
对于每一个a[i], 都会使ans[j](j = i + k， k = 0, 1, 2, ……)加1，而对于每一个相等的a[i]和a[j]，显然 ans[i] = ans[j]。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//Mystery_Sky
//
#define M 10000100
int cnt[M], ans[M], a[M];
int n, maxx;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
maxx = max(a[i], maxx);
cnt[a[i]]++;
}
for(int i = 1; i <= maxx; i++) {
if(cnt[i]) for(int j = i; j <= maxx; j += i) ans[j] += cnt[i];
}
for(int i = 1; i <= n; i++) printf("%d
", ans[a[i]]-1);
return 0;
}