fork(10) download
copy 
  1. // Written by Vasanth Raja Chittampally
  2. // Source Code: Sieve of Eratosthenes
  3. // All rights are reserved
  4.  
  5. #include <math.h>
  6. #include <iostream>
  7. #include <time.h>
  8. void seive(int start, int range, int * primes)
  9. {
  10. 	//Seiving is done here
  11. 	long start1 = clock();
  12. 	for(int i = 6; i <= sqrt((float)range); i++)
  13. 	{
  14.  
  15. 			int iter = 2 * i + 1;
  16. 			if(primes[i] == 1)
  17. 			{
  18. 				int startInLoop = start / iter;
  19. 				if(startInLoop % 2 == 0)
  20. 					startInLoop++;
  21. 				if(startInLoop < 13)
  22. 					startInLoop = 13;
  23. 				for(int j = startInLoop * iter; j <= range ; j += 2 * iter)
  24. 					primes[(j - 1) / 2] = 0;
  25. 			}
  26. 	}
  27. 	std::cout<<std::endl<<"Time for Seive of Eristhones: "<< (double)(clock()-start1) / CLOCKS_PER_SEC<<std::endl;
  28. 	int count = 0;
  29. 	// display the results
  30. 	std::cout<<std::endl<<"Prime numbers with in the given range are"<<std::endl;
  31. 	for(int i = start / 2; i <= range / 2; i++)
  32. 		if(primes[i] != 0)
  33. 		{
  34. 			std::cout<< 2 * i + 1 << " ";
  35. 			count++;
  36. 		}
  37. 	std::cout<<std::endl<< "Total number of primes between "<<start<<" and "<<range<<"  are : " << count << std::endl;
  38. }
  39. int main(void)
  40. {
  41. 	int start;
  42. 	int end;
  43. 	std::cin>>start;
  44. 	std::cin>>end;
  45. 	int * primes = new int[end / 2 + 1];
  46. 	long time1 = clock();
  47. 	for(int i = 0; i <= end / 2; i++)
  48. 	{
  49. 			primes[i] = 1;
  50. 	}
  51. 	for(int i = 4; i <= end / 2; i += 3)
  52. 	{
  53. 			primes[i] = 0;
  54. 	}
  55. 	for(int i = 7; i <= end / 2; i += 5)
  56. 	{
  57. 			primes[i] = 0;
  58. 	}
  59. 	for(int i = 10; i <= end / 2; i += 7)
  60. 	{
  61. 			primes[i] = 0;
  62. 	}
  63. 	for(int i = 16; i <= end / 2; i += 11)
  64. 	{
  65. 			primes[i] = 0;
  66. 	}
  67. 	double totTime = (double)(clock() - time1) / CLOCKS_PER_SEC;
  68. 	std:: cout << std::endl<<"Time for 2 3 5 7 11 : " <<totTime<< std::endl ;
  69. 	seive(start, end, primes);
  70. 	return 0;
  71. }
  72.  
Success #stdin #stdout 0s 2864KB
comments (?)
stdin
copy 
10
100
stdout
copy 
Time for 2 3 5 7 11 : 0

Time for Seive of Eristhones: 0

Prime numbers with in the given range are
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 
Total number of primes between 10 and 100  are : 22
https://ideone.com/PsxKp
language:
C++ (gcc 8.3)
created:
12 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!