欧拉函数

题目描述

功能:输入一个正整数，按照从小到大的顺序输出它的所有质数的因子（如180的质数因子为2 2 3 3 5 ）

最后一个数后面也要有空格  

详细描述：

函数接口说明：

public String getResult(long ulDataInput)

输入参数：

long ulDataInput：输入的正整数

返回值：

String

 

 

输入描述:

输入一个long型整数

输出描述:

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

示例1

输入

复制 180

输出

复制 2 2 3 3 5 1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 int main() 5 { 6 long n,nt; 7 while(cin>>n) 8 { 9 nt=n; 10 for(int i=2;i<=int(sqrt(n));i++) 11 { 12 while(nt%i==0) 13 { 14 cout<<i<<" "; 15 nt/=i; 16 } 17 } 18 if(nt!=1) cout<<nt<<" "; 19 cout<<endl; 20 } 21 return 0; 22 } View Code

【欧拉函数（初级）φ函数】https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/1944850?fr=aladdin

 

 

 

 题目描述 给你一个正整数n，请问有多少个比n小的且与n互质的正整数？ 两个整数互质的意思是，这两个整数没有比1大的公约数。 输入 输入包含多组测试数据。每组输入是一个正整数n（n<=1000000000）。当n=0时，输入结束。  输出 对于每组输入，输出比n小的且与n互质的正整数个数。  样例输入 7 12 0  样例输出 6 4  1 #include<iostream> 2 typedef long long ll; 3 using namespace std; 4 ll oula(ll n) 5 { 6 ll ans=n; 7 for(ll i=2;i<=n;i++) 8 { 9 if(n%i==0) ans=ans/i*(i-1); //欧拉函数 10 while(n%i==0) n/=i; //筛法选素数 11 } 12 return ans; 13 } 14 int main() 15 { 16 ll n; 17 while(cin>>n&&n) 18 { 19 cout<<oula(n)<<endl; 20 } 21 return 0; 22 } View Code

 

题目描述 https://www.luogu.org/problemnew/show/P1592

输入两个正整数n和k，求与n互质的第k个正整数。

输入输出格式

输入格式：

 

仅一行，为两个正整数n(≤10^6)和k(≤10^8)。

 

输出格式：

 

一个正整数，表示与n互质的第k个正整数。

 

输入输出样例

输入样例#1：  10 5 输出样例#1： 11  题解： https://www.luogu.org/problemnew/solution/P1592 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e6+5; 4 int a[N],cnt; 5 int main() 6 { 7 int n,k; 8 scanf("%d%d",&n,&k); 9 for(int i=1;i<n;i++) 10 if(__gcd(i,n)==1) 11 a[++cnt]=i; 12 printf("%d",(k-1)/cnt*n+a[(k-1)%cnt+1]); 13 return 0; 14 } View Code

 

转载于:https://www.cnblogs.com/qing123tian/p/11123091.html

相关资源：欧拉函数计算 C语言实现