fork download
copy 
  1. #include <stdio.h>
  2. #include<math.h>
  3. const int MAX = 100000000;
  4. const int LMT = 10000;
  5. #define ifcV(x)  (flag[x>>6]&(1<<((x>>1)&31)))
  6. #define iscV(x)  (flag[x>>6]|=(1<<((x>>1)&31)))
  7. int flag[100000000>>6];
  8. long int a[5000010],total;
  9. void seive()
  10. 	{
  11. 		long int i,j,count=1;
  12. 		for(i=3;i<LMT;i=i+2)
  13. 		{
  14. 			if(!ifcV(i))
  15. 			{
  16. 				for(j=i*i;j<=MAX;j+=2*i)//Here increment by 2*i bcoz we are considering only odd numbers.In normal seive we consider all no.s so there we increment by i
  17. 					iscV(j);
  18. 			}
  19. 		}
  20.  
  21. 		a[0]=2;
  22. 		for(i=3;i<=MAX&&count<5000003;i+=2)
  23. 			{
  24. 				if(!ifcV(i))
  25. 				a[count++]=i;
  26. 			}
  27. 			total=count;
  28. 	}
  29.  
  30. int BS(int st, int fn, int val)
  31. {
  32.     int mid;
  33.     while(st <= fn)
  34.     {
  35.         if(val < a[st]) return st-1;
  36.         if(val > a[fn]) return fn;
  37.         mid = (st+fn) / 2;
  38.         if(val == a[mid]) return mid;
  39.         else if(val < a[mid]) fn = mid-1;
  40.         else st = mid+1;
  41.     }
  42.     return total-1;
  43. }
  44. int main(void) {
  45.  
  46. 	seive();
  47. 	while(1)
  48. 	{int x;
  49. 	int i;
  50. 	double ans;
  51. 	scanf("%d",&x);
  52. 	if(x==0)
  53. 	return 0;
  54. 	i=BS(0, total-1, x);
  55.  
  56. 	ans=((i-x/log(x))/i)*100.0;
  57.  
  58.  
  59. 	if(ans<0)
  60. 	ans= - ans;
  61.  
  62. 		printf("%.1lf\n",ans);
  63. 	}
  64.  
  65.  
  66. }
  67.  
Success #stdin #stdout 0.8s 27648KB
comments (?)
stdin
copy 
10000000
2
3
5
1234567
0
stdout
copy 
6.6
inf
173.1
55.3
7.7
https://ideone.com/7k3PsO
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!