Hi everyone.
I have just finished my PRIME1 program, but I am for some reason getting WA. I can't see the problem. I am using Sieve of Eratosthenes and the program finishes in 0.09 s.
#include <stdlib.h>
#include <stdio.h>
char primetbl[100000];
void PRIME1(int m, int n) {
/* SET ALL BUT 0 AND 1 TO PRIME STATUS */
int i;
for (i=0; i <= n-m; i++) {
primetbl[i] = 1;
}
if (m == 1) {
primetbl[0] = 0;
}
/* MARK ALL THE NON-PRIMES */
int thisFactor = 2;
int lastSquare = 0;
int thisSquare = 0;
while (thisFactor * thisFactor <= n) {
/* MARK THE MULTIPLES OF THIS FACTOR */
int mark = thisFactor + thisFactor;
if (mark < m) {
mark = m+thisFactor-(m%thisFactor);
}
while (mark <= n) {
primetbl[mark-m] = 0;
mark += thisFactor;
}
/* PRINT THE PROVEN PRIMES SO FAR */
thisSquare = thisFactor * thisFactor;
if (thisSquare > m) {
if (lastSquare < m) {
lastSquare = m;
}
for (; lastSquare < thisSquare; lastSquare++) {
if (primetbl[lastSquare-m]) {
printf("%d\n", lastSquare);
}
}
}
else {
lastSquare = thisSquare;
}
/* SET thisFactor TO NEXT PRIME */
thisFactor++;
while (thisFactor >= m && primetbl[thisFactor-m] == 0) {
thisFactor++;
}
}
/* PRINT THE REMAINING PRIMES */
for (; lastSquare <= n; lastSquare++) {
if (primetbl[lastSquare-m]) {
printf("%d\n", lastSquare);
}
}
}
int main() {
int num, i;
int m, n; // 1 <= m <= n <= 1000000000
fscanf(stdin, "%d\n", &num);
for (i=0; i < num; i++) {
fscanf(stdin, "%d %d\n", &m, &n);
PRIME1(m, n);
if (i+1 < num) {
printf("\n");
}
}
return 0;
}
Can anyone see the problem?
I wish SPOJ could give me more info about why and where it failed...
