首页 > 代码库 > UVa 10299 - Relatives
UVa 10299 - Relatives
题目:计算一个给定数的欧拉函数(1~n-1中和n互质的数的个数)。
分析:数论,素数筛法,欧拉函数。
欧拉函数:φ(n)= n *(1 - 1/p1)*(1 - 1/p2)*(1 - 1/p3)*…*(1 - 1/pt);
这里利用筛法打表计算出50000内的素数,因为数据范围是1000000000内的,
所以,不能被前50000内的素数整除的数,也一定是素数,并且每个数n中最多有一个;
计算输出即可。
说明:UVa10179。
#include <iostream> #include <cstdlib> using namespace std; int fac[30]; int prim[50000]; int used[50000]; int main() { for (int i = 0 ; i < 50000 ; ++ i) used[i] = 0; int save = 0; for (int i = 2 ; i < 50000 ; ++ i) if (!used[i]) { prim[save ++] = i; for (int j = 2*i ; j < 50000 ; j += i) used[j] = 1; } int n; while (cin >> n && n) { int count = 0,base = 0,m = n; while (n > 1 && base < save) { if (n%prim[base] == 0) { fac[count ++] = prim[base]; while (n%prim[base] == 0) n /= prim[base]; } base ++; } if (n > 1) fac[count ++] = n; long long ans = m; for (int i = 0 ; i < count ; ++ i) ans = ans/fac[i]*(fac[i]-1); if (n == 1) ans = 0LL; cout << ans << endl; } return 0; }
UVa 10299 - Relatives
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。