fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. int isPrimefast(unsigned long long int x);
  4.  
  5. int main() 
  6. { 
  7. int casen; 
  8. scanf("%d\n", &casen); 
  9. while(casen--) 
  10. {
  11.  
  12.  
  13. unsigned long long  int n,m,count,count1,jj,kk,ii,dd,fact,just1,just2;
  14. unsigned long long int i,p;
  15. int j;
  16. count=0,count1=0; 
  17. scanf("%lld %lld\n",&n,&m);
  18. just1=n;
  19. just2=m;
  20. //count=count+issquare(n,m);
  21. //printf("no of squares------>%llu\n",issquare(n,m));
  22. //unsigned long long int * primes = new unsigned long long int[m-n+1]; 
  23. unsigned long long int primes[m-n+1];
  24. //initialising
  25. jj=sqrt(just1);
  26. //printf("Value of jj---> %llu\n",jj);
  27. kk=sqrt(just2);
  28. //printf("jj---->%llu kk---->%llu count1 ------>%llu\n",jj,kk,count1);
  29. if(jj*jj!=just1)
  30. {
  31. jj=jj+1;
  32. //printf("I did enter\n");
  33. }
  34. //printf("Value of jj---> %llu\n",jj);
  35. for(ii=jj;ii<kk+1;ii++)
  36. {   fact=0;
  37. 	for(dd=1;dd<ii;dd++)
  38. 	{
  39. 	if((ii*ii)%dd==0)
  40. 	{
  41. 	//printf("This qualified as a no %llu\n");
  42. 	fact++;
  43.     }
  44.     }
  45. 	if(isPrimefast((fact*2)+1)==1)
  46. 	{
  47. 	//printf("Factors of the no is %llu\t ",(fact*2)+1);
  48. 	//printf("This no qualifies %llu\n",ii*ii);
  49. 	count1++;
  50.     }
  51.  
  52. }
  53.  
  54. //printf("Count1----> %llu\n",count1);
  55. //printf("count now %llu\n",count);
  56. for(i=0;i<m-n+1;++i) 
  57. primes[i] = 0; 
  58. for(p=2;p*p<=m;++p) 
  59. { 
  60. unsigned long long int less = n / p;
  61.  less *= p; 
  62.  // first number <= N && p divides N 
  63.  for(j=less;j<=m;j+=p) 
  64.  {
  65.  
  66.     if(j != p && j >= n) 
  67.     primes[j - n] = 1; 
  68.  }
  69.  } 
  70.  for(i=0;i<m-n+1;++i) 
  71.  { 
  72.  if(primes[i] == 0 && n+i != 1)
  73.  {  
  74.    	count++;
  75.    	//printf("count value increased to %llu",count);
  76.  } 
  77.  
  78.  // We don't want to print if it's 1 
  79.  //printf("%lld\n",n+i); 
  80.  }
  81.  //count=count+count1;
  82.  printf("%llu",count+count1); 
  83.  if(casen) 
  84.  printf("\n"); 
  85.  //delete [] primes; 
  86.  }
  87.  return 0; 
  88.  } 
  89. int isPrimefast(unsigned long long int x)
  90. {   
  91. 	 long long int k,j;
  92. 	k=sqrt(x);
  93. 	//printf("k----->%lld\n",k);
  94.  
  95. 	if(x==1)
  96. 	return 0;
  97. 	if(x==2)
  98. 	return 1;
  99. 	if(x==3)
  100. 	return 1;
  101. 	if(x==4)
  102. 	return 0;
  103. 	if(x==5)
  104. 	return 1;
  105.  
  106. 	if((x-1)%6==0||(x+1)%6==0||x%2!=0||x%3!=0||x%5!=0||x%7!=0)
  107. 	{
  108.  
  109. 	for(j=2;j<k+1;j++)
  110. 	{   
  111.  
  112.  
  113. 		if(x%j==0)
  114. 		return 0;
  115.  
  116. 	}
  117. 	return 1;
  118.     }
  119.     else
  120.     return 0;
  121. }
Success #stdin #stdout 5.34s 11040KB
comments (?)
stdin
copy 
50
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
stdout
copy 
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
78687
1000001
https://ideone.com/A4BRfV
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!