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