《linux 内核完全剖析》 chapter 8 内核代码

求n内与n互质的数有多少个。

欧拉函数就是为这个而生的。

如果对欧拉函数不是很了解的话,可以看看这个http://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

我们有了上一篇埃氏筛法求素数之后,我们求这个就简单了。

具体用法就是这个函数


用最后这个公式。n可以写成

我们先来求得2到sqrt(n)的素数然后来将n化成的形式

中间如果n能整除p的话就要带入公式了。这样我们就求得最后结果了。

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
	bool b[10000];
	memset(b,true,sizeof(b));
	for(int i=2;i<10000;i++)
	{
		if(b[i])
		{
			for(int j=i+i;j<10000;j+=i)
			{
				b[j]=false;
			}
		}
	}
	//上面为埃氏筛法筛素数 下面是欧拉函数的应用
	int n;
	while(cin>>n)
	{
		int nn=n;
		int ans=n;
		int ii=2;
		while(n&&ii*ii<(nn))
		{
			if(b[ii]&&n%ii==0)
			{
				ans=ans-ans/ii;
				while(n%ii==0)
				{
					n/=ii;
				}
			}
			ii++;
		}
		cout<<ans<<endl;
	}
	system("pause");
}

好了!

感谢自己坚持。

《linux 内核完全剖析》 chapter 8 内核代码,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。