102 Coprimes

单独求欧拉函数

#include <iostream>
3

#include <cmath>
4

using namespace std;
5

int euler(int x) {
7

int i, res = x;
8

for(i = 2; i < (int)(sqrt(x * 1.0))+1; i++) {
9

if(!(x % i))
10

res = res / i * (i-1);
11

while(!(x % i))
12

x /= i;
13

}
14

if(x > 1)
15

res = res / x * (x-1);
16

return res;
17

}
18

int main() {
20

int n;
21

cin >> n;
22

cout << euler(n) << endl;
23

return 0;
24

}

posted on 2010-01-21 14:25 安子阅读(5) 评论(0) 编辑收藏引用

2026年6月

日

一

二

三

四

五

六