poj 2773 Happy 2006

#include<cstdio>
#define N 1000001
using namespace std;
int n,k,cnt,prime[N],phi[N],t,m;
bool v[N],ok;
void get_euler()
{
    phi[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!v[i])
        {
            v[i]=true;
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(i*prime[j]>N) break;
            v[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int gcd(int a,int b)
{
    return !b ? a:gcd(b,a%b);
}
int main()
{
    get_euler();
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n==1)
        {
            printf("%d\n",k);
            continue;
        }
        ok=false;
        m=k/phi[n];
        t=k-phi[n]*m;
        if(!t) m--,t=phi[n];
        for(int i=n*m+1;;i++)
        {
            if(gcd(n,i)==1) t--;
            if(!t)
            {
                printf("%d\n",i);
                break;
            }
        }
    }
}

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
bool check[1000001];
int euler(int n)//埃式筛法模板 
{
    int m=int(sqrt(n+0.5));
    int ans=n,k=n;
    memset(check,0,sizeof(check));
    for(int i=2;i<=m;i++)
     if(n%i==0)
     {
         ans=ans/i*(i-1);
         for(int j=1;i*j<=k;j++)
          check[i*j]=true;
         while(n%i==0) n/=i;
     }
    if(n>1)
    {
        ans=ans/n*(n-1);
        for(int j=1;n*j<=k;j++) 
         check[n*j]=true;
    }
    return ans;
}
int main()
{
    int m,k,ans,cnt,t,i;
    while(scanf("%d%d",&m,&k)!=EOF)
    {
        ans=euler(m);
        cnt=0;
        if(k%ans==0) t=k/ans-1;
        else t=k/ans;
        k=k-ans*t;
        for(i=1;i<=m;i++)
        {
            if(!check[i]) cnt++;
            if(cnt==k) break;
        }
        printf("%d\n",i+m*t);
    }
}