第k个互质的数求解。

Question

第k个互质的数
题目描述
输入两个正整数n和k，求与n互质的第k个正整数。
输入格式
仅一行，为两个正整数n(n≤10000)和k(≤1000000)。
输出格式
一个正整数，表示与n互质的第k个正整数。
输入输出样列
输入样例1：复制
10 5
输出样例1：复制
11
【耗时限制】1000ms 【内存限制】128MB

Answer 1

#include<iostream>
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    int n,k,sum=0,a=0,i=1;
    cin>>n>>k;
    while(sum!=k){
        if(gcd(n,i)==1){
            sum++;
            a=i;
        }
        i++;
    }
    cout<<a;
    return 0;
}