Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- int main()
- {
- int ar[100001]={0},i,j,n=1000001,t,tot[100001],k;
- for(int p=0;p<n;p++)
- tot[p]=p;
- for(i=2;i<n;i++)
- {
- if(!ar[i])
- {
- for(j=i;j<n;j+=i)
- {
- ar[j]=1;
- tot[j]*=i-1;
- tot[j]/=i;
- }
- }
- }
- scanf("%d",&t);
- while(t--)
- {
- scanf("%d",&k);
- printf("%d\n",tot[k]);
- }
- }
Add Comment
Please, Sign In to add comment