fork download
copy 
  1. /*
  2.  *  This file uses the Erastothenes Sieve way of producing Primes
  3.  *
  4.  *  Created on: Jun 4, 2012
  5.  *      Author: mirtchea
  6.  
  7.  
  8. Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
  9. Input
  10.  
  11. The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
  12. Output
  13.  
  14. For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
  15. Example
  16.  
  17. Input:
  18. 2
  19. 1 10
  20. 3 5
  21.  
  22. Output:
  23. 2
  24. 3
  25. 5
  26. 7
  27. 3
  28. 5
  29.  
  30. */
  31.  
  32. // calculate the amount of time needed to generate 10 sets of the highest prime numbers
  33.  
  34. #include <stdio.h>
  35. #include <math.h>
  36. #include <time.h>
  37.  
  38. int main()
  39. {
  40. 	int num; // the number of test cases
  41. 	bool singleArray[100000]; // holds one range of prime numbers: TRUE if prime, FALSE otherwise
  42. 	static unsigned long allArray[1000000]; // holds all of the ranges of prime numbers
  43. 	unsigned long nums[10][2]; // the array of numbers that hold all the ranges
  44. 							   // 10 rows, 2 columns (10 sets of numbers, with two numbers each)
  45. 	unsigned long s; 	   // holds the square root of the upper end of the range
  46. 	long n1, n2; // the two numbers in each range, read in 'num' number of times
  47.     int count = 0;  // maintains the count of all the prime numbers to be stored into the final array
  48.     long intermediate; // used for the range of the array to track the index of the found prime numbers
  49. 	//time_t start, end;   /// stores the start and end time of the operation
  50.  
  51. 	scanf("%d", &num);
  52.  
  53. 	for(int i = 0; i < num; ++i) // for the number of test cases, gather the pairs of numbers
  54. 	{
  55. 		scanf("%lu", &n1);  // the first number being scanned in
  56. 		scanf("%lu", &n2);  // the second number being scanned in
  57. 		nums[i][0] = n1;   // store the first number in the array
  58. 		nums[i][1] = n2;   // store the second number in the array
  59. 	}
  60.  
  61. 	//time(&start);
  62. 	for(int i = 0; i < 100000; ++i)  // set all the values in the single range array to TRUE
  63. 	{
  64. 		singleArray[i] = true;
  65. 	}
  66.  
  67. 	for(int i = 0; i < num; ++i) // go through all the test cases
  68. 	{
  69. 		s = sqrt(nums[i][1]);
  70. 		for(unsigned long k = 2; k <= s; ++k)  // for all the numbers ranging from 2, to the square root of the upper range
  71. 		{
  72. 			for (unsigned long j = nums[i][0]; j <= nums[i][1]; ++j) // for all the numbers in each test range
  73. 			{
  74. 				intermediate = j - nums[i][0];
  75. 				if(!singleArray[intermediate])  // if the current location is already false, this means that the number is a non-prime
  76. 				{
  77. 					continue;
  78. 				}
  79. 				if((j % k == 0 && k != j) || (j == 1))		// otherwise, divide into the current number; for numbers that divide evenly, set that value to FALSE (for not being a prime number)
  80. 				{
  81. 					singleArray[intermediate] = false;
  82. 				}
  83. 			}
  84. 		}
  85.  
  86. 		// for the single array, copy back into the main array
  87. 		for(unsigned long m = nums[i][0]; m <= nums[i][1]; ++m) // for the range of numbers in one set
  88. 		{
  89. 			intermediate = m - nums[i][0];
  90. 			if(singleArray[intermediate])  //if the number in the single array is a prime, store into the general array
  91. 			{
  92. 				allArray[count++] = m;
  93. 			}
  94. 		}
  95. 		//reset all the array values to true
  96. 		for(int p = 0; p < (nums[i][1] - nums[i][0]); ++p)
  97. 		{
  98. 			singleArray[p] = true;
  99. 		}
  100. 	 }
  101.  
  102. 	// print all the prime numbers in the larger array
  103. 	for(int n = 0; n < count; ++n)
  104. 	{
  105. 		printf("%lu\n", allArray[n]);
  106. 	}
  107.  
  108. 	//time(&end);
  109.  
  110. 	//printf("This operation took: %.02f seconds to execute \n", difftime(end,start));
  111.  
  112. }
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
Success #stdin #stdout 0s 23048KB
comments (?)
stdin
copy 
2
1 10
3 5
stdout
copy 
2
3
5
7
3
5
https://ideone.com/IHr7pq
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

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!