document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. //
  2. //  PRIME1.c
  3. //  2. Prime Generator
  4. //
  5. //  Created by Catarina Moreira on 09/01/13.
  6. //  Copyright (c) 2013 Catarina Moreira. All rights reserved.
  7. //
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11.  
  12. #define IS_PRIME 0
  13. #define NOT_PRIME 1
  14.  
  15. int NUM_TESTS;      // total tests to perform
  16. int M;          // starting number
  17. int N;          // ending number
  18.  
  19. /* ******************** FUCNTION DECLARATIONS ******************** */
  20.  
  21. // Generates all primes up to N
  22. void prime_generator(int *list);
  23.  
  24. // Creates a new integer list of size N wth all values are considered PRIMES
  25. int *create_integer_list(int * my_list);
  26.  
  27. // Prints the prime numbers according to the output format
  28. void print_results(int *list, int t );
  29.  
  30. /* ******************** MAIN FUCNTION ******************** */
  31.  
  32. int main(int argc, const char * argv[])
  33. {
  34.     scanf("%d", &NUM_TESTS);    // read total test cases from input
  35.  
  36.     int t;
  37.     for (t = 0; t < NUM_TESTS; t++)
  38.     {
  39.         scanf("%d %d", &M, &N);     // read input data    
  40.         if( M == 1) M = 2;
  41.  
  42.         int * my_list;
  43.         my_list = create_integer_list(my_list);    // creates a new integer list of size N-M
  44.  
  45.         prime_generator(my_list);          // generate primes up to N-M
  46.  
  47.         print_results(my_list, t );        // print computed primes
  48.  
  49.         free(my_list);                 // removes list 
  50.         my_list = NULL;
  51.     }                                              
  52.     return EXIT_SUCCESS;
  53. }
  54.  
  55. /* ******************** AUXILIARY FUNCTIONS ******************** */
  56.  
  57. // Prime generator
  58. void prime_generator(int *list)
  59. {
  60.     int i, j;
  61.    
  62.     for( i = 2; i*i <= N; i++)
  63.     {
  64.         // Find the first number less than M that the prime number 2 divides evenly
  65.     int lower_bond = M / i;          // Divide M by the prime number (integer division)
  66.     lower_bond *= i;             // Multuply M by the prime number
  67.        
  68.     for( j = lower_bond; j <= N; j+= i)  // find all multiples of lower_bond
  69.         if( j != i && j >= M)
  70.         list[j - M] = NOT_PRIME;        // and update the entries to NOT_PRIME
  71.     }
  72. }
  73.  
  74. // Creates a new integer list of size N wth all values are considered PRIMES
  75. int *create_integer_list(int * my_list)
  76. {
  77.     my_list = (int *)calloc( (N - M + 1)  , sizeof(int));
  78.        
  79.     if (my_list == NULL)
  80.         puts("[CREATE_INTEGER_LIST] Memory allocation failed.");
  81.    
  82.     return my_list;
  83. }
  84.  
  85. // Prints the prime numbers according to the output format
  86. void print_results(int *list, int t )
  87. {  
  88.     int i;
  89.     for(i=0; i <= N-M; i++ )
  90.         if( list[i] == IS_PRIME)
  91.         printf("%d\\n", i+M);
  92.    
  93.     if( t + 1 != NUM_TESTS) printf("\\n");
  94. }
');