sizeof和strlen

求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");
}

感谢自己坚持。

sizeof和strlen,布布扣,bubuko.com

sizeof和strlen

原文：http://blog.csdn.net/jymn_chen/article/details/25335949