fork download 
  1. /*
  2. 	Author      : akgarhwal
  3. 	Date        : 30-05-2017 21:12:49
  4. 	Description : Language Used -> C++14
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef unsigned long long	ll;
  11. typedef vector<int>	vi;
  12. typedef pair<int,int>	pi;
  13. #define F		first
  14. #define S		second
  15. #define PB		push_back
  16. #define MP		make_pair
  17. #define sz(a)		int((a).size())
  18. #define all(c)		(c).begin(),(c).end()
  19. #define REP(i,a,b)	for(int i = a; i < b; i++)
  20. #define tr(c,i)		for(auto i = (c).begin(); i != (c).end(); i++)
  21. #define present(c,x)	((c).find(x) != (c).end())
  22. #define cpresent(c,x)	(find(all(c),x) != (c).end())
  23. #define MOD		1000000007 	/* 10^9+7*/
  24.  
  25. vector<bool> prime(10000001,true);
  26. long long a[100005];
  27.  
  28. int main(){
  29.  
  30. 	//prime calculating using seive
  31. 	prime[1]=false;	
  32. 	vector<ll> p;
  33. 	for(ll i=2; i< 10000001; i++){
  34. 		if(prime[i]){
  35. 			for(int j=i+i; j< 10000001; j+=i){
  36. 				prime[j]  = false;
  37. 			}
  38. 		}
  39.  
  40. 	}
  41. 	//push prime to vector p
  42. 	for(int i=2; i<10000001 ; i++){
  43. 		if(prime[i]){
  44. 			p.PB(i);
  45. 		}
  46. 	}
  47.  
  48. 	//vector<bool>().swap(prime);
  49. 	ll A,b;
  50. 	cin>>A>>b;
  51.  
  52. 	int ind=0;
  53. 	for(ll i=A; i<=b ; i++){
  54. 		a[ind++] = i;
  55. 	}
  56.  
  57. 	int N = sz(p);
  58.  
  59. 	for(int i=0; i< N ; i++){
  60.  
  61. 		ll P = p[i];
  62. 		ll c = P-(A%P);
  63. 		if(P == c){
  64. 			a[0] = (a[0]/P)*(P-1LL);
  65. 		}
  66. 		for(ll j=c; j<= b-A; j+=P){
  67. 			a[j] = (a[j]/P)*(P-1LL);				
  68. 		}
  69. 	}
  70.  
  71. 	for(int i=0; i<=b-A ; i++){
  72. 		if(a[i] == i+A and i+A>1){
  73. 			a[i]--;
  74. 		}
  75. 		cout<<a[i]<<"\n";
  76. 	}
  77.  
  78. 	return 0;
  79. }
Success #stdin #stdout 0.07s 16848KB
comments (?)
stdin 
1 10
stdout 
1
1
2
2
4
2
6
4
6
4
https://ideone.com/3IMO41
language:
C++ (gcc 8.3)
created:
9 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!