fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define n 1000001
  3. using namespace std;
  4. int a[n];
  5. void init(){
  6. for(int i=0;i<n;i++){
  7. 	a[i]=i;
  8. 	}
  9.  
  10. for(int i=2;i*i<n;i++){
  11.  
  12. 	if(a[i]==i){
  13.    for(int j=i;j<n;j+=i){
  14.  
  15.    	a[j]/=i;
  16.    	a[j]*=(i-1);
  17.         }
  18. 	}
  19. }
  20.  
  21. }
  22. int main(){
  23. init();
  24. int t,x;
  25. cin>>t;
  26. while(t--){
  27. 	cin>>x;
  28. 	cout<<a[x]<<endl;
  29. }
  30.  
  31.  
  32. 	return 0;
  33. }
Success #stdin #stdout 0.01s 7416KB
comments (?)
stdin
copy 
5
1
2
3
4
5
stdout
copy 
1
1
2
2
4
https://ideone.com/JsYYAR
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!