fork(21) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int N = 1000010;
  6. int lp[N+1];
  7. vector<int> pr;
  8.  
  9. void init()
  10. {
  11.     for (int i=2; i<=N; ++i) 
  12. 	{
  13. 		if (lp[i] == 0) 
  14. 		{
  15. 			lp[i] = i;
  16. 			pr.push_back (i);
  17. 		}
  18. 		for (int j=0; j<pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
  19. 			lp[i * pr[j]] = pr[j];
  20. 	}
  21. }
  22.  
  23.  
  24. int count(int n)
  25. {
  26. 	int ans = 0;
  27. 	int curprime = 0;
  28. 	while (n!=1)
  29. 	{
  30. 		int minp = lp[n];
  31. 		if (minp != curprime) ++ans, curprime = minp;
  32.  
  33. 		n/=minp;
  34. 	}
  35. 	return ans;
  36. }
  37.  
  38. int f(int a, int b, int c)
  39. {
  40. 	int cnt = 0;
  41. 	for (int i = a; i <= b; ++i)
  42. 		if (count(i)==c)
  43. 			++cnt;
  44. 	return cnt;
  45. }
  46.  
  47.  
  48. int main()
  49. {
  50. 	init();
  51. 	int a, b, c; 
  52. 	cin>>a>>b>>c;
  53. 	cout<<f(a,b,c);
  54. }
  55.  
Success #stdin #stdout 0.1s 6892KB
comments (?)
stdin
copy 
2 1000000 1
stdout
copy 
78734
https://ideone.com/rMTIBj
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!