Trying again
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!
Leave a Comment