SPOJ PRIME1

Here is another one of those problems that any wannabe programmer should solve to get initiated in the art of problem solving (trying to preach here ;)) . This code got me through, barely though.

It tends to be pretty slow, one must try segmented sieve for problems like this. But after I got an ACC I was not in a mood to dive into it again. Hopefully, someday I'll return to it and give it a second look. Till then ...

#include<cstdlib>

#include<iostream>

#include<string>

#include<fstream>

#include<cmath>

#include<cstring>

using namespace std;

#define SZ 32000




bool prime_tab[SZ];




int main(int argc, char** argv) {

int m, n, t;

prime_tab[0] = prime_tab[1] = 1;

for (int i = 2; i < SZ; i++) {

if (!prime_tab[i]) {

for (int j = 2; i * j < SZ; j++) {

prime_tab[i * j] = 1;

}

}

}







cin >> t;

while (t--) {

cin >> m >> n;







for (int i = m; i <= n; i++) {

bool pass = (i != 1);

for (int j = 2; j * j <= i; j++) {

if (!prime_tab[j]) {

if (i % j == 0) {

pass = 0;

break;

}

}




}

if (pass)

cout << i << endl;







}

cout << endl;




}

return 0;

}