SPOJ 2 - PRIME1 - Prime Generator

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input

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.

Output

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.

Example

text

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

Solution

First, use the Sieve of Eratosthenes Method to calculate all prime numbers under sqrt(n). For each composite number between m and n, it must have a prime factor small or equal then sqrt(n), so just enumerate each prime number to eliminate non-prime numbers. One important point: for each prime p, we have no need to check composite numbers less then p^2, it's quite an important way to accelerate the caculation.

By the way, this method is usally called Segmented Sieve of Eratosthenes.

And I use some bit operations for reducing memory use.

Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define IS_PRIME(is_prime, n) ((is_prime[(n) >> 3] >> ((n) & 0x07)) & 0x01)

#define SET_NOT_PRIME(is_prime, n) is_prime[(n) >> 3] &= 0xff ^ (1 << ((n) & 0x07))

/*
 * Function: sieve
 * -------------------------------
 *  Use Sieve of Eratosthenes Method to compute all prime numbers small or equals given upper bound.
 *
 *  max_n: upper bound of prime numbers.
 *  prime_count: will be assigned in this function representing the length of the result.
 *
 *  returns: an array of prime numbers or NULL.
 */
long *sieve(long max_n, long *prime_count) {

  long i, j, sqrt_n = floor(sqrt(max_n)), length = (max_n >> 3) + 1;
  long *prime_numbers;

  unsigned char *is_prime = (unsigned char*) malloc(sizeof(unsigned char) * length);

  memset(is_prime, 0xff, sizeof(unsigned char) * length);

  for (i = 2; i <= sqrt_n; i++) {

    if (IS_PRIME(is_prime, i)) {


      for (j = i + i; j <= max_n; j += i) {

        SET_NOT_PRIME(is_prime, j);
      }
    }
  }

  for (i = 2, *prime_count = 0; i <= max_n; i++) {

    if (IS_PRIME(is_prime, i)) {

      (*prime_count)++;
    }
  }

  if (0 == *prime_count) {

    free(is_prime);

    return NULL;
  }

  prime_numbers = (long *)malloc(sizeof(long) * (*prime_count));

  for (i = 0, j = 2; j <= max_n; j++) {

    if (IS_PRIME(is_prime, j)) {

      prime_numbers[i++] = j;
    }
  }
    
  free(is_prime);

  return prime_numbers;
}

/*
 * Function: segmented_sieve
 * -------------------------
 *  Use Segmented Seive Method to compute all prime numbers with given closed interval.
 *
 *  m: lowwer bound of prime numbers.
 *  n: upper bound of prime numbers.
 *  prime_count: will be assigned in this function representing the length of the result.
 *
 *  returns: an array of prime numbers or NULL.
 */
long *segmented_sieve(long m, long n, long *prime_count) {

  long small_prime_count;
  long *small_prime_numbers = sieve(floor(sqrt(n)), &small_prime_count);
  
  long length = n - m + 1, i, j, p;
  
  unsigned char *is_prime = (unsigned char*) malloc(sizeof(unsigned char) * length);
  
  long *prime_numbers;

  memset(is_prime, 0xff, sizeof(unsigned char) * length);
 
  if (small_prime_count > 0) {

    for (i = 0; i < small_prime_count; i++) {

      p = small_prime_numbers[i];

      j = p * p;

      if (m >= j) {

        j = m;

        if (j % p != 0) {

          j += (p - j % p);
        }
      }

      for (; j <= n; j += p) {

        SET_NOT_PRIME(is_prime, j - m);
      }
    }

    free(small_prime_numbers);
  }

  for (i = m, *prime_count = 0; i <= n; i++) {

    if (i >= 2 && IS_PRIME(is_prime, i - m)) {

      (*prime_count)++;
    }
  }

  if (0 == *prime_count) {

    free(is_prime);
    
    return NULL;
  }

  prime_numbers = (long *)malloc(sizeof(long) * (*prime_count));

  for (i = 0, j = m; j <= n; j++) {

    if (j >= 2 && IS_PRIME(is_prime, j - m)) {

      prime_numbers[i++] = j;
    }
  }

  free(is_prime);

  return prime_numbers;
}

int main(int argc, char **argv) {

  long prime_count, *prime_numbers;

  long t, m, n, i;

  scanf("%ld", &t);

  while (t--) {

    scanf("%ld%ld", &m, &n);

    prime_numbers = segmented_sieve(m, n, &prime_count);

    if (prime_count > 0) {

      for (i = 0; i < prime_count; i++) {

        printf("%ld\n", prime_numbers[i]);
      }

      free(prime_numbers);
    }

    if (t) {

      printf("\n");
    }
  }

  return 0;
}