Skip to content

Trying again

August 14, 2011

Same code – spoj prime1:

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


Okay! It looks like the bracketed sourcecode tags work nicely!

From → Uncategorized

Leave a Comment

Leave a comment