资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

　　互质数个数

问题描述

　　已知正整数x，求1~x-1中，有多少与x互质的数。（互质是指两个数最大公约数为1）

输入格式

　　输入一行包括一个正整数x

输出格式

　　共一行，只有一个整数，表示与x互质数的个数

样例输入

12

样例输出

4

数据规模和约定

　　x<=10^8

样例说明

　　有1,5,7,11四个数与12互质。

法一：试除法

#include<iostream>
using namespace std;

int main(){
	int n;
	cin>>n;
	long long res=n;
	for(int i=2;i<=n/i;i++){
		if(n%i==0){
			res=res*(i-1)/i;
			while(n%i==0){//除干净 
				n/=i;
			}
		}
	}
	if(n>1) res=res*(n-1)/n; 
	cout<<res<<endl;
}

注意： 题目中输入的n<=10^8，因此在计算的过程中可能超出int范围，所以用long long类型。

法二：线性筛法，但运行错误，因为N过大

#include<iostream>
using namespace std;
const int N=1e8+10;
int p[N],vis[N],phi[N];
int cnt;
int main(){
	int n;
	cin>>n;
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			p[cnt++]=i;
			phi[i]=i-1;
		}
		for(int j=0;i*p[j]<=n;j++){
			int m=i*p[j];
			vis[m]=1;
			if(i%p[j]==0){
				phi[m]=p[j]*phi[i];
				break;
			}else{
				phi[m]=(p[j]-1)*phi[i];
			}
		}
	}
	cout<<phi[n];
	return 0;
}