List primes within an interval

I'm trying to solve the SPOJ primes problem:


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


Input:

2
1 10
3 5

Output:

2
3
5
7

3
5

Warning: large Input/Output data, be careful with certain languages
(though most should be OK if the algorithm is well designed)

Due to the warning, I use a segmented sieve of Eratosthenes, having found the primes between 1 and 32000 with a normal sieve:

```
#include

int find_primes(int begin, int end)
{

int i;
int y = 0;
int z = 0;
int primes[3402] = {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,14

Your solution is, in fact, conceptually quite clever. There are some style issues, some bugs, and some optimizations...
So ... Magic numbers

You have the prepared list of primes, and you declare the array as length 3402. Why specify the length when if you leave it blank, the compiler will do it for you? Anyway, when I counted, there are 3401....

int primes[] = {3,5,......};

Then, in your loop, you set the limit at 3399 ... why? Well, element 3399 is prime 31607 which is the largest prime who's square (999002449) is less than 1000000000... OK.

So, you have magic numbers.... I would define them and move on... having them as constant numbers in the code is confusing.
Bugs

Your code does not successfully output 2, ever. You need to work on that edge case.
Variables

The names are all wrong, except the array primes.

I would use p instead of i, as it is not a classic i++ for loop.

y and z are meaningless.... use a variable name that makes sense, like isprime and i
Performance

There are two things I can suggest to improve performance....

-
If begin or end are less than primes[3400] then you can do a binary-search on primes and then just output those primes while they fall within the primes array, and between begin and end. No need for calculations.....

-
Your inner z loop scanning primes should terminate when primes[z] > sqrt(i). At the moment, if i is 31, you are scanning all 3400 primes to see if they are factors.... ouch.

StackExchange Code Review Q#58818, answer score: 2