互质数的个数

　

互质数

给定一个整数 nn，请问有多少个整数 i满足条件：gcd(i, n) = 1，1<=i<=n;

输入格式

输入一行，输入一个整数 n(n<=10^9)。

输出格式

输出一行，输出一个整数，表示符合条件的整数个数。

样例输入

16

样例输出

8

超时： 

#include<iOStream>
#define MAX 1000000000
using namespace std;
int gcd(int a,int b)
{
	return b==0 ?a:gcd(b,a%b);
}
int main()
{
	int n,count=0;
	cin>>n;
	for(int i=1;i<n;++i)
	{
		if(gcd(i,n)==1)
		{
			count++;
		}
	}
	cout<<count;
	return 0;
}

超内存 :

#include<iostream>
#include<vector>
#define MAX 1000000000
using namespace std;
bool map[MAX];
void prime(int n)
{
	map[0]=map[1]=1;
	for(int i=2;i*i<n;++i)
	{
		if(!map[i])
		{
			for(int j=i*i;j<n;j+=i)
			{
				map[j]=1;
			}
		}
	}
}
int gcd(int a,int b)
{
	return b==0 ?a:gcd(b,a%b);
}
int main()
{
	int n;
	cin>>n;
	prime(n);
	float count=(float)n;
	for(int i=1;i<n;++i)
	{
	   if(!map[i]&&(n%i==0))
	   {
		 count*=(1-1/(float)i);
	   }
	}
	printf("%.0f",count);
	return 0;
}

ac代码解析：

主要的还是在套公式，其中的while循环是亮点

#include <iostream>
using namespace std;
int euler(int n)
{
    int  res=n;
    for(int i=2;i*i<=n;i++)
	{
		//因为是在遍历因子，所以找一半就行了
        if(n%i==0)
		{
			//cout<<"因子 = "<< i<<" 此时n = ";
			//如果i是n的第一个因子即最小那个
            res=res/i*(i-1);
			//公式变形：
			//∮(n) = n*(1-P1)/P1*……*（1-Pn)/Pn
			//cout<<n<<endl;
            while(n%i==0)
			{
				//寻找下一个质因子
                n/=i;
			   //cout<<"while 中 = "<<n<<endl;
            }
           // cout<<"出while后 = "<<n<<endl;
        }
        
    }
    if(n>1)
	{
		//大于sqrt(n)的质因子会导致循环提前结束，如42 = 2*3*7
        res=res/n*(n-1);
    }
    return res;
}


int main()
{
    int n;
    cin>>n;
    cout<<euler(n);
    //euler(30);
    return 0;
}

相关阅读

求两个数的平均值三种方法

第一种 最常见的方法两个数相加然后除以2获得平均值。int ave(int x, int y) { return (x + y) >> 1; } 因为c语言中整数有存储

合并两个数组的方法

1.数组的方法concat():concat();方法为赋值并新增，返回一个新数组，只适合无嵌套的数组，concat();会将数组最外层的中括号去掉，然后对

26个英文字母（大小写）+10个数字

大写：ABCDEFGHIJKLMNOPQRSTUVWXYZ 小写：abcdefghijklmnopqrstuvwxyz 数字：0123456789

求两个数最大公因数的c语言程序

对于这个问题,我能想到的方法有三种: ①先找出这两个数中最小的那个,可以用i表示,然后用这两个数依次对i取余. 同时i不断减1,直到

【C】质因数的个数

题目描述 求正整数N(N>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。 输入描述: 可能有多组测