题目大意：找小于N的互素数个数。
解决方法1：对从1~N的每个数求它与N的最大公约数，如果等于1读数器加1，最后输出结果。
解决方法2：对从1~N的数组遍历，如果这个数没有被处理过(一定是质数)，则判断它是否能被N整除，如果可以，则这个质数的所有倍数都一定不与N互素；如果不可以，则这个质数一定不与N互素，而它的倍数可能与N互素。处理一遍后，计算可能互素及一定互素的数的个数。
下面只贴方法2的代码：
#include <iostream>
using namespace std;
int num[10001];
int main() {
int i, j, N, cnt = 0;
memset(num,-1,sizeof(num));
num[0] = 1, num[1] = 3;
cin >> N;
for(i = 2; i <= N; i++) {
if(num[i] != -1) continue;
if(N%i == 0) {
// must not
for(j = i; j <= N; j += i)
num[j] = 1;
}
else {
// must be
num[i] = 3;
for(j = i+i; j <= N; j += i)
num[j] &= 7;
}
}
for(i = 1; i <= N; i++) {
if((num[i] & 3) == 3) cnt++;
}
cout << cnt << endl;
return 0;
}
posted on 2011-05-31 17:56
古月残辉 阅读(328)
评论(0) 编辑 收藏 引用 所属分类:
SGU