Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // PRIME1.c
- // 2. Prime Generator
- //
- // Created by Catarina Moreira on 09/01/13.
- // Copyright (c) 2013 Catarina Moreira. All rights reserved.
- //
- #include <stdio.h>
- #include <stdlib.h>
- #define IS_PRIME 0
- #define NOT_PRIME 1
- int NUM_TESTS; // total tests to perform
- int M; // starting number
- int N; // ending number
- /* ******************** FUCNTION DECLARATIONS ******************** */
- // Generates all primes up to N
- void prime_generator(int *list);
- // Creates a new integer list of size N wth all values are considered PRIMES
- int *create_integer_list(int * my_list);
- // Prints the prime numbers according to the output format
- void print_results(int *list, int t );
- /* ******************** MAIN FUCNTION ******************** */
- int main(int argc, const char * argv[])
- {
- scanf("%d", &NUM_TESTS); // read total test cases from input
- int t;
- for (t = 0; t < NUM_TESTS; t++)
- {
- scanf("%d %d", &M, &N); // read input data
- if( M == 1) M = 2;
- int * my_list;
- my_list = create_integer_list(my_list); // creates a new integer list of size N-M
- prime_generator(my_list); // generate primes up to N-M
- print_results(my_list, t ); // print computed primes
- free(my_list); // removes list
- my_list = NULL;
- }
- return EXIT_SUCCESS;
- }
- /* ******************** AUXILIARY FUNCTIONS ******************** */
- // Prime generator
- void prime_generator(int *list)
- {
- int i, j;
- for( i = 2; i*i <= N; i++)
- {
- // Find the first number less than M that the prime number 2 divides evenly
- int lower_bond = M / i; // Divide M by the prime number (integer division)
- lower_bond *= i; // Multuply M by the prime number
- for( j = lower_bond; j <= N; j+= i) // find all multiples of lower_bond
- if( j != i && j >= M)
- list[j - M] = NOT_PRIME; // and update the entries to NOT_PRIME
- }
- }
- // Creates a new integer list of size N wth all values are considered PRIMES
- int *create_integer_list(int * my_list)
- {
- my_list = (int *)calloc( (N - M + 1) , sizeof(int));
- if (my_list == NULL)
- puts("[CREATE_INTEGER_LIST] Memory allocation failed.");
- return my_list;
- }
- // Prints the prime numbers according to the output format
- void print_results(int *list, int t )
- {
- int i;
- for(i=0; i <= N-M; i++ )
- if( list[i] == IS_PRIME)
- printf("%d\n", i+M);
- if( t + 1 != NUM_TESTS) printf("\n");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement