Segmented sieve using C

[1vf9z8AR]

Here is my segmented sieve. Any tips to make the program run faster?

Also please check if my method is correct.

  #include<stdio.h>
#include<math.h>
int main()
{
    int t,m,n;
    scanf("%d",&t);
    int prime[100000],root=sqrt(1000000000);
        for(int i=2;i*i<=root;i++)
        {
            if(prime[i]!=1)
            {
                for(int mult=2;i*mult<=root;mult++)
                {
                    prime[i*mult]=1;
                }
            }
        }
    while(t>0)
    {
        scanf("%d%d",&m,&n);
        if(m==1)
            m+=1;
        for(int x=m;x<=n;x++)
        {
            int fa=1;
            for(int y=2;y<=sqrt(n);y++)
            {
                if(prime[y]!=1)
                {
                    if(x%y==0 && x!=y)
                        fa=0;
                }
            }
            if(fa==1)
                printf("%d\t",x);
        }
        t-=1;
    }
}

[1vf9z8AR]

plz help me

[keskiverto]

Why do you precompute a large sieve? Why not just the amount that you do need for n?

You have:

int prime[100000];
if ( prime[2] != 1 )

That produces undefined behaviour, because uninitialized array could have value 1 in its elements.


You do have the sieve. Non-prime elements are 1 in it. Isn't prime[x] != 1 if x is prime?

[dhayden]

Any tips to make the program run faster?

Precompute sqrt(n) before line 26. Right now you're computing it each time, although the optimizer might be smart enough to remove it.

Break out of the loop at line 31. Once you set fa=0, there's no reason to continue through the loop.

Line 26-28 basically say "for each number 2 to sqrt(n), if it's prime then do something". You might be better off storing the actual primes as you compute them in the first part of the program. Then your loop could be "for each prime from 2 to sqrt(n), do something"

please check if my method is correct

You allocate space for primes though 100,000, but you're only computing them through 31622 (sqrt(1,000,000,000)). Is that your intention?

[jonnin]

if you keep your known primes and start finding them at 2, I believe you can just use your primes list to look for factors. that is, say you were checking 1337.

the sqrt of 1337 is ~36.
so we need to check the primes from 2 to 37
2? nope
3? nope
5? nope
7? yes, not prime.

but you didn't need to check 4,6, etc. this is significant for larger values. (basic number theory stuff but if you look, 4 is checked by checking 2. nothing exists that has 4 as a factor but not 2 as a factor. nothing exists that has 6 as a factor but not 2 and 3, etc).

another way to do it even faster is to take the GCD of a running multiple of all the primes, if you want to support large values. That is, 2*3*5*7*11*13... each one you find, you multiply the value into the running product. If yu don't support very large integers, this falls flat in a hurry.

[dhayden]

If yu don't support very large integers, this falls flat in a hurry

Not necessarily. You can keep a vector of products of primes and do the GCD test on all items in the vector. I recently came across a program that used this method on the HP-41C calculator about 30 years ago.

[jonnin]

Yes. I have no idea what the big-O of that approach is! That is nontrivial... do you think it beats just brute force dividing by your growing list of known primes? Primes cluster in the first million or so and then spread out... maybe a hybrid of those 2 is in order... 2 or 3 of the prime 'factorials' (primorials? do these guys have a math name yet?) and then go brute force on the primes past those as they spread out?

Ill be honest, I am terribly lazy and terribly fond of lookup tables. I had a table of the first million primes and never needed anything bigger (I did not do encryption though) and another of the first 100 or so factorials... I never bothered with all this generation stuff.