Skip to content

Longer Test – Prime1

August 14, 2011

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;
}

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: