//
// 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");
}