# Longer Test – Prime1

This tests the code brackets using SPOJ problem prime1:

Input

The input begins with the number t of test cases in a single line. 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.

#include <iostream>

#include<stdio.h>

#include<cmath>

#include <string.h>

using namespace std;

int main()

{

static bool isprime[100001];

bool extendisprime[190001];

// load bottom of array;

isprime[0] = true;

isprime[1] = true;

long long mult;

// sieve to weed out non primes for initial array

// if not a prime set value to "true" (counterintuitive, but faster since array initialixzed at "false").

for( long long i = 2; i < 10001; i++)

{

if (isprime[i] == false)

{

for (mult = i; i*mult < 100001; mult++)

{

isprime[i*mult] = true;

}

}

// increase by two if i is not initially two (this makes it jump by odd numbers for faster transversal).

if (i!=2)

{

i++;

}

//loading up extended prime array.

}

int iter;

long long bottom,top;

long long bottom2;

bottom = 10; // I don't remember why I did this.

cin>>iter; // iter <= 10 according to rules

for (int i = 0; i < iter; i++)

{

cin>>bottom>>top; //1 <= bottom <= top <= 1000000000 according to rules.

if (top > 100000)

{

memset(extendisprime, false, 190001);// reset array if not empty.

for (long long j = 2; j*j <= top+1&&j<100001; j++)

{

if (isprime[j] == false)

{

// find a number divisible by j and greater than or equal to the bottom of the sample.

if (bottom%j > 0)

{

bottom2 = bottom/j;

bottom2 = bottom2*j;

while (bottom2 < bottom)

{

bottom2 += j;

}

}

else

{

bottom2 = bottom;

}

while (bottom2 <= top) // mark all multiples of j between the bottom and the top nonprime.

{

if (j != bottom2)

{

extendisprime[bottom2 – bottom] = true;

}

bottom2 += j;

}

}

}

}

if (i>0)

printf("\n");// blank line between iterations

for (long long k = bottom; k <=top; k++)

{

if (top <= 100000)

{

if (!isprime[k])

{

printf("%lld\n",k);

}

}

else

{

if (!extendisprime[k – bottom])

{

//cout<<k<<endl;

printf("%lld\n",k);

}

}

}

}

return 0;

}