I am using segmented sieve of Eratosthenes to solve the Prime Generator problem on SPOJ. On my system it gives me correct results, but when I submit it gives me WA. Can anyone please tell what is wrong in my code?
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
using vc = vector<char>;
void smallPrimes(vc &sPrimes, const unsigned long &sqrt_n) {
for (unsigned long i = 2; i < sqrt_n; ++i) {
if (sPrimes[i])
for (long j = i+i; j < sqrt_n; j += i)
sPrimes[j] = false;
}
}
void strikeComposites(vc &nums, const vc &sPrimes, const unsigned long &m) {
for (unsigned long j = 2, ss = sPrimes.size(); j < ss; ++j)
if (sPrimes[j])
for (unsigned long i = 0, ns = nums.size(); i < ns; ++i) {
unsigned long temp = m+i;
if ((temp % j == 0) && (temp != j)) {
nums[i] = false;
}
}
}
int main() {
int t;
scanf("%d",&t);
while (t--) {
unsigned long m,n;
scanf("%ld%ld",&m,&n);
unsigned long sqrt_n = sqrt(n);
vc sPrimes(sqrt_n+1,true);
smallPrimes(sPrimes,sqrt_n+1);
vc nums(n-m+1,true);
strikeComposites(nums, sPrimes, m);
for (long i = 0, ns = nums.size(); i < ns; ++i) {
if (nums[i] && i+m != 1 && i+m != 0)
printf("%ld\n",i+m);
}
}
return 0;
}
FIX:
Thanks @leppyr64 I came to know what was wrong with my code. In my code I was expecting the difference of m and n to be 10000. While in the question statement it was given that n-m <= 100000.
NOTE: The above code is now correct. For the previous code click this link.