fork download
copy 
  1. #include<stdio.h>
  2. //#include<math.h>
  3. #define true 1
  4. #define false 0
  5. typedef unsigned long long ulong;
  6. int prime[1000000];
  7.  
  8.  
  9. ulong power(ulong a,int n){
  10. if(n==0)
  11. return 1;
  12. if(n&1){
  13. ulong p=power(a,n>>1);
  14. return a*p*p;
  15. }
  16. else
  17. {
  18. ulong p=power(a,n>>1);
  19. return p*p;
  20. }
  21. }
  22.  
  23. int returnIndex(int i,ulong l){
  24. if(i>l)
  25. return 2;
  26. int j;
  27. for(j=2;j<100;j++){
  28. if(!prime[j-1]){
  29. if(power(i,j-1)>=l)
  30. {
  31. return j;
  32. }
  33. }
  34. }
  35. }
  36. void sieve(){
  37. int i;
  38. for(i=2;i<=1000;i++){
  39. int p=1-1%i;
  40. if(i*i>p)
  41. p=i*i;
  42. if(p==i || p<1)
  43. p+=i;
  44. while(p<=1000000){
  45. prime[p-1]=true;
  46. p+=i;
  47. }
  48. }
  49. }
  50. int main(){
  51. int t;
  52. scanf("%d",&t);
  53. sieve();
  54. while(t-->0){
  55. ulong l,r;
  56. scanf("%llu",&l);
  57. scanf("%llu",&r);
  58. int size=r-l+1;
  59. int input[size];
  60. // printf("Here I Am\n");
  61. // printf("Here I Am\n");
  62. int i,j;
  63. for(i=0;i<size;i++)
  64. input[i]=1;
  65. //mark all prime powers of primes...
  66. for(i=2;i<=r && i<1000000;i++){
  67. if(!prime[i-1]){
  68. int rem = l%i;
  69. int index=0;
  70. if(rem!=0)
  71. index = i-rem;
  72. for(j=index;j<size;j+=i){
  73. if((j+l)==i)
  74. {input[j]=1;
  75. //printf("applying 1 on j=%llu for i=%d\n",j+l,i);
  76. }
  77. else{	
  78. // printf("unmarking %llu for i=%d\n",j+l,i);
  79. input[j]=0;
  80. }
  81. }
  82. }
  83. }
  84. //printf("prime powers successfully done.\n");
  85. // for(i=0;i<size;i++)
  86. // printf("mark=%d i=%d value=%llu\n",input[i],i,i+l);
  87. for(i=2;i<=r && i<1000000;i++){
  88. if(!prime[i-1]){
  89. int ret = returnIndex(i,l);
  90. for(j=ret;j>0;j++){
  91. if(!prime[j-1]){
  92. ulong temp=power(i,j-1);
  93. if(temp>r){
  94. break;
  95. }
  96. else{
  97. input[temp-l]=1;
  98. //printf("marking it back %llu for i=%d\n",temp,i);
  99. }	
  100. }
  101. }
  102. }
  103. }	
  104. int count=0;
  105. if(l==1)
  106. input[0]=0;
  107. for(i=0;i<size;i++){
  108. if(input[i]){
  109. //printf("%llu\n",i+l);
  110. count++;
  111. }
  112. }
  113. printf("%d\n",count);
  114. }
  115. }
Success #stdin #stdout 0.12s 9984KB
comments (?)
stdin
copy 
1 
999999000000 1000000000000
stdout
copy 
36400
https://ideone.com/js1rMM
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!