首页 > > 程序设计 > C/C++ >

欧拉函数

2018-10-03 17:57:01来源：博客园阅读 ()

欧拉函数：（转自百度百科）

欧拉函数F（x）的作用：求从1到x与x互质的数的个数。

直接求欧拉函数

int euler(int n)//计算与n互质的数的个数
{
    int res = n,maxn = n;
    for(int i=2;i*i < maxn;i++)
    {
        if(n % i == 0)
        {
            res = res / i * (i-1);
            while(n % i == 0)//去除n中所有的i的倍数
                n /= i;
        }
    }
    if(n > 1)//最后还剩一个因子，也要算上
        res = res / n * (n-1);
    return res;
}

对一段区间内的数进行求欧拉函数，并打表

int euler[maxn];
void init(int maxn)
{
    euler[1] = 1;
    for(int i=2;i < maxn;i++)
        euler[i] = i;
    for(int i=2;i < maxn;i++)
    {
        if(euler[i] == i)
        {
            for(int j=i;j < maxn;j++)//对所有包含质因数i的数进行求欧拉函数值
            {
                euler[j] = euler[j] / i * (i-1);//先进行除法，是为了防止中间有数据溢出
            }
        }
    }
    return ;
}

点击打开链接UVA10820

题意：给出一个数n，问从1到n有多少对互质的数

HINT：（1,1）是互质的；

连续卡了几天的欧拉函数，在今天终于顿悟，虽然然不是很透彻，赶紧记下来，哈哈哈哈。。

这个题找到一对互质的数后，记得将他们两个互换也是符合条件的。这样求出总的互质的对数后乘以2就OK了。

等等！！！有个小坑就是（1,1）互换后是一样的。。。。。额，有点小尴尬。没事最后的数减去1就OK了。

上代码：

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 50010;
int buf[maxn];

void init()
{
    memset(buf,0,sizeof(buf));
    buf[1] = 1;//边筛选素数，边计算合数的欧拉函数
    for(int i=2; i <= maxn; i++) //当前的数是被筛到的数的质因子,当buf[i]为0是，代表buf[i]是素数
    {
        if(buf[i] == 0)//如果该数是素数
        {
            for(int j=i; j <= maxn; j+=i)//找到质因子中包含该数的合数
            {
                if(buf[j] == 0)
                    buf[j] = j;
                //计算合数的欧拉函数
                buf[j] = buf[j]/i*(i-1);
            }
        }
    }
    for(int i=2;i <= maxn;i++)
    {
        //printf("buf[i-1]: %d  ",buf[i-1]);
        buf[i] += buf[i-1];
    }
    //printf("buf[2]:%d\n",buf[2]);
}
int main()
{
    int n;
    init();
    while(scanf("%d",&n) && n)
    {
        printf("%d\n",2*buf[n]-1);
    }
    return 0;
}