SPOJ - Prime Generator (PRIME1)
SPOJ link: PRIME1
Peter wants to generate some prime numbers for his crypto system. 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:
Input:
2
1 10
3 5
Output:
2
3
5
7
3
5
My Solution: the Sieve of Eratosthenes
|
1. Create a boolean empty list of size N - M + 1, and consider that all entries are PRIMES.
2. Choose the first prime. Since 2 is the lowest prime known we start with it. 3. Find the number less than M that can evenly divide it by the chosen prime number. This is done by making an integer division between M and the prime number and then multiplying M by the prime number. 4. With the number found in the previous step, find all multiples of that number and update the entries of your list to NOT_PRIME. 5. Choose the next prime and repeat the process until prime_chosen * prime_chosen <= N. 6. Return all entries of the list that are marked as PRIME |
 |