PRIME1: pc's terminal prints correct output, SPOJ shows "Time Limit Exceeded", ideone prints incorrect one, codeforces custom test won't even output

general
,
1

EDIT: was able to identify the fault (still didn’t fix the whole thing, so not sure), but the I increment the i inside the loop, which should cause some false primevectors, not sure how it worked on my terminal though

After trying to implement the sieve of eratosthenes and finally get it right (at least I think I did), the SPOJ result is time limit exceeded, tried to execute it in ideone to see how much time it takes, ideone prints incorrect output, not sure what’s happening?

SPOJ Question

IDEone trial

And this is what my terminal prints after execution and providing the same input

2

3

5

7

[There is an extra line here]

3

5

Code:

#include <iostream>
#include <string>
#include <sstream> 
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;

void findPrimes(int min,int max){
    if(min == 1)
        min++;
    int vectorsize = int(sqrt(max-1));
    vector<bool> primesVector(vectorsize,true);
    int arrSize = max-min+1;
    bool mArr[arrSize];
    for(int i=0;i<vectorsize;i++){
        if(primesVector[i] == true){
            i += i+2;
            while(i<vectorsize){
                primesVector[i] = false;
                i += i+2;
            }
        }
    }
        
    for(int i=0;i<vectorsize;i++){
        if(primesVector[i]){
            for(int j=0;j<arrSize;j++){
                if((j+min)%(i+2)==0){
                    if((j+min)==(i+2))
                        j += i+2;
                    while(j<arrSize){
                        mArr[j] = true;
                        j += i+2;
                    }
                }
            }
        }
    }
    for(int j=0;j<arrSize;j++){
        if(mArr[j] == false)
            cout << j+min << endl;
    }
}

int main () {
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int min, max;
        cin >> min >> max;
        findPrimes(min,max);
        if(i<n-1)
            cout << endl;
    }
    return 0;
}
2

we can’t help you unless we see your code.

3

Here is my code it works perfectly

/**
*  SPOJ: Prime Generator -- PRIME1-----Prime no sucks
*/
//amitt001
#include<stdio.h>
#include<string.h>
int prime[10000], primes;

void init_primes(){
    int n =32000;
    int isprime[n];
    int i,j;
    memset(isprime, 1, sizeof(isprime));
    for(i=2; i<n; i++)
        if(isprime[i])
        {
            for(j=2*i; j<n; j+=i)
                isprime[j]=0;
        }
    primes = 0;
    for(i = 2 ; i < n; i++){
        if(isprime[i])
            prime[primes++]=i;
    }

}

int seive[100001];

void find_seive(int lo, int hi){
   int i,j,p,n;
     memset(seive, 1, sizeof(seive));
   for(j=0;;j++){
       p=prime[j];
       if(p*p > hi) break;// a better way to check till sqrt(hi)-- usual codes use math.h and sqrt which makes the code slower
       n = (lo/p)*p;      //segmented sieve part- VVVV IMPORTANT
       if(n<lo)
        n+=p;
       if(n==p)
        n+=p;
       for(;n<=hi; n+=p)
          seive[n-lo]=0;
   }
}

int main(){
    int t,m,n,i;
    init_primes();
    scanf("%d", &t);//>>t;
    while(t--){
        scanf("%d%d", &m, &n);//>>m>>n;
        if(m<2)
            m=2;
        find_seive(m,n);
        for(i =0; i<=n-m; i++){
            if(seive[i]){
                printf("%d\n", m+i);//<<m+i<<"\n";//check
            }
        }
        printf("\n");
    }
}