fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. bool primes[1000001];
  5. int prime[300000] = {};
  6. int idx = 0;
  7.  
  8. int angka[1000001];
  9.  
  10. void sieve(int n){
  11. 	for(int i=2; i*i<=n; i++){
  12. 		if(primes[i]){
  13. 			for(int j=i*i; j<=n; j+=i){
  14. 				primes[j]=false;
  15. 			}	
  16. 		}
  17. 	}
  18. }
  19.  
  20. int degree(int n){
  21. 	float sq= sqrt(n);
  22. 	int count=0;
  23. 	if(primes[n]) return 1;
  24. 	for(long long i=0; prime[i]<=sq && n != 1; i++ ){
  25. 		bool nope=false;
  26. 		if(n%prime[i]==0) {
  27. 			while(n%prime[i]==0){
  28. 				if(nope) return 0;
  29. 				n/=prime[i];
  30. 				nope = true;
  31. 			}
  32. 			count++;
  33. 			if(primes[n]) {
  34. 				count++;
  35. 				n = 1;
  36. 			} 
  37. 		}
  38. 		if(n==0) return count;
  39. 	}
  40. 	return count;
  41. }
  42.  
  43. int main(){
  44. 	memset(primes, 1, sizeof(primes));
  45. 	sieve(1000000);
  46.  
  47. 	for(int i = 2; i < 1000001; i++) {
  48. 		if(primes[i]) {
  49. 			prime[idx++] = i;
  50. 		}
  51. 	}
  52.  
  53. 	angka[1]= -1;
  54. 	for(int i=2; i<1000001; i++){
  55. 		angka[i]=degree(i);
  56. 	//	printf("%d %d\n",i,angka[i]);
  57. 	}
  58.  
  59. 	int t;
  60. 	scanf("%d",&t);
  61. 	for(int ti=1; ti<=t; ti++){
  62. 		int l,r,k;
  63. 		int cnt=0;
  64. 		scanf("%d %d %d",&l,&r,&k);
  65. 		for(int i=l; i<=r; i++){
  66. 			if(angka[i]==k){
  67. 				cnt++;
  68. 			}
  69. 		}
  70. 		printf("Case #%d: %d\n",ti,cnt);
  71. 	}
  72. }
Success #stdin #stdout 0.06s 21288KB
comments (?)
stdin
copy 
3
1 10 1
1 10 2
10 14 3
stdout
copy 
Case #1: 4
Case #2: 2
Case #3: 0
https://ideone.com/CJmjlB
language:
C++ (gcc 8.3)
created:
4 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!