officeyutong

欧拉函数

作者：

officeyutong

在

, ,

设函数$$\phi (x)$$为不超过x且与x互素的正整数的个数(两个数互素，则两个数的最大公因数为1)

则$$\phi(x)=x(1-\frac {1} {p_1})(1-\frac {1} {p_2})(1-\frac {1} {p_3})(1-\frac {1} {p_4})·····(1-\frac {1} {p_n})$$

其中$$p_n$$为将x通过唯一分解定理所得的式子的底数，即$$n={p_1}^{k_1} {p_2}^{k_2} {p_3}^{k_3} {p_4}^{k_4} …..{p_m}^{k_m} $$ 其中$$p_n$$为素数

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using int_t = long long int;

int_t func(int_t x) {
    int_t result = x;
    for (int_t i = 2; i <= x; i++) {
        //如果x的可以整除i,则结果中i的指数+1
        if (x % i == 0) {
            //    result = result * (i - 1) / i;
            //先乘后除防止溢出
            result = result / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) result = result / x * (x - 1);
    return result;
}

int main() {
    int_t x;
    while (cin >> x) {
        int_t result = func(x);
        cout<

或者可以通过类似于线性筛素数的方式求出一定范围内所有的数的欧拉函数值


#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
using int_t = long long int;
const int_t MAX = 100000;
int_t phi[MAX + 1];
int main() {
    int_t x;
    cin>>x;
    memset(phi, 0, sizeof (phi));
    phi[1] = 1;
    for (int_t i = 2; i <= x; i++) {
        if (phi[i] == 0) {
            for (int_t j = i; j <= x; j = j + i) {
                if (phi[j] == 0) phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
        }

    }
    for(int_t i=1;i<=x;i++) cout<<"phi("<<i<<") = "<<phi[i]<<endl;

}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章