fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define int long long
  4. #define pb emplace_back
  5. #define endl '\n'
  6. typedef vector<int> vi;
  7. #define sz(a) (int)((a).size())
  8.  
  9. void setUpLocal()
  10. {
  11. #ifndef ONLINE_JUDGE
  12. 	freopen("/Users/asuryana/Documents/CP/input.txt", "r", stdin);
  13. 	freopen("/Users/asuryana/Documents/CP/output.txt", "w", stdout);
  14. #endif
  15. }
  16.  
  17. void fio()
  18. {
  19. 	ios_base::sync_with_stdio(false);
  20. 	cin.tie(NULL);
  21. }
  22.  
  23. const int maxN = 1e6 + 1;
  24.  
  25. bitset<maxN> isPrime; // used in sieve()
  26.  
  27. vi primes; //vector which contains all primes
  28.  
  29. int spf[maxN];// smallest prime factor
  30.  
  31. vi prime_factor[maxN]; // stores number of prime factors using prime factorization
  32.  
  33. void sieve()
  34. {
  35. 	isPrime.set();// init all to 1;
  36. 	isPrime[0] = isPrime[1] = 0;
  37.  
  38. 	for (int i = 2; i < maxN; i += 2)
  39. 	{
  40. 		spf[i] = 2;
  41. 		isPrime[i] = (i == 2);
  42. 		prime_factor[i].pb(2);
  43. 	}
  44. 	for (int i = 3; i < maxN; i += 2)
  45. 	{
  46. 		if (isPrime[i])
  47. 		{
  48. 			for (int j = i; j < maxN; j += i)
  49. 			{
  50. 				prime_factor[j].pb(i);
  51. 				if (isPrime[j] and j != i)
  52. 				{
  53. 					spf[j] = i;
  54. 					isPrime[j] = 0;
  55. 				}
  56. 			}
  57. 		}
  58. 	}
  59. 	for (int i = 2; i < maxN; i++)
  60. 		if (isPrime[i])
  61. 		{
  62. 			primes.pb(i);
  63. 		}
  64.  
  65. }
  66.  
  67. int numberOfDivisors(int n)
  68. {
  69. 	int nod = 1;
  70.  
  71. 	if (isPrime[n]) // useful check for higher primes. :p
  72. 	{
  73. 		return 2;
  74. 	}
  75.  
  76. 	int idx = lower_bound(primes.begin(), primes.end(), spf[n]) - primes.begin();
  77. 	//2^20 = 1,048,576. so  binary search on 20 elements is o(1). safe assumption.
  78.  
  79. 	for (int j = idx ; j < primes.size(); j++)
  80. 	{
  81. 		int i = primes[j];
  82. 		int cnt = 0;
  83. 		if (n % i == 0)
  84. 		{
  85. 			while (n % i == 0)
  86. 			{
  87. 				n /= i;
  88. 				cnt ++;
  89. 			}
  90. 		}
  91. 		nod *= (cnt + 1);
  92. 	}
  93.  
  94. 	if (n > 1)
  95. 	{
  96. 		nod *= 2;
  97. 	}
  98.  
  99. 	return nod;
  100.  
  101. }
  102.  
  103. bool ok(int no) // no = p*q (p and q are distinct primes) is possible?
  104. {
  105. 	return (sz(prime_factor[no]) == 2 and (prime_factor[no][0] * prime_factor[no][1] == no));
  106. }
  107.  
  108. void solve()
  109. {
  110. 	int c = 0;
  111. 	sieve();
  112.  
  113. 	for (int i = 1; i <= 999927; i++) // last number is given in spoj
  114. 	{
  115. 		int nod = numberOfDivisors(i); //O(log i) max divisors for i
  116.  
  117. 		if (ok(nod))//O(1) // # of prime_factors for nod = p*q or not. checking this.
  118. 		{
  119. 			c++;
  120. 			if (c % 9 == 0)
  121. 			{
  122. 				cout << i << endl;
  123. 			}
  124. 		}
  125. 	}
  126. }
  127.  
  128. int32_t main()
  129. {
  130. 	fio();
  131. 	setUpLocal();
  132. 	return solve(), 0;
  133. }
  134.  
Time limit exceeded #stdin #stdout 5s 82080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rgqZ3R
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!