C++

Forum

 
Segmented sieve

closed account (1vf9z8AR)
This is my segmented sieve. Please help me. Why is it not working?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
  #include<stdio.h>
int main()
{
    int t,m,n;
    scanf("%d",&t);             // number of test cases
    while(t>0)
    {
        scanf("%d%d",&m,&n);
        int prime[n];           // for finding prime numbers
        int listofprime[n];     // for storing only prime numbers
        int pos=0;
        for(int i=2;i<=n;i++)     //declare all to 1
            prime[i]=1;
        prime[0]=0;
        prime[1]=0;
        for(int i=2;i*i<=n;i++)           //simple sieve to find primes till sqrt(n)
        {
            if(prime[i]==1)
            {
                listofprime[pos]=i;
                pos++;
                for(int mult=2;i*mult<=n;mult++)
                    prime[i*mult]=0;
            }
        }
        for(int i=0;listofprime[i]*listofprime[i]<=n;i++)    //segmented sieve
        {
            int low=m/listofprime[i];
            low*=listofprime[i];
            for(int j=low+listofprime[i];j<=n;j+=listofprime[i])
                prime[j]=0;
        }
        for(int i=m;i<=n;i++)                   // print all prime numbers
        {
            if(prime[i]==1)
                printf("%d\n",i);
        }
        t-=1;
    }
}
LajosOnly (31)
You read a place in your Array, that doesn't exist!
An Array always beginning with 0 and ends with the number of places - 1.

In your for Loop for(int i=2;i*i<=n;i++) you ask for a place as big as n, that won't work.
closed account (1vf9z8AR)
so array size should be n+1?
LajosOnly (31)
Yes, if the Array size is n + 1 the last place will be n or you can change "<=" to "<".
Last edited on
closed account (1vf9z8AR)
It's still not working. I declared array size as n+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
 #include<stdio.h>
int main()
{
    int t,m,n;
    scanf("%d",&t);             // number of test cases
    while(t>0)
    {
        scanf("%d%d",&m,&n);
        int prime[n+1];           // for finding prime numbers
        int listofprime[n+1];     // for storing only prime numbers
        int pos=0;
        for(int i=2;i<=n;i++)     //declare all to 1
            prime[i]=1;
        prime[0]=0;
        prime[1]=0;
        for(int i=2;i*i<=n;i++)           //simple sieve to find primes till sqrt(n)
        {
            if(prime[i]==1)
            {
                listofprime[pos]=i;
                pos++;
                for(int mult=2;i*mult<=n;mult++)
                    prime[i*mult]=0;
            }
        }
        for(int i=0;listofprime[i]*listofprime[i]<=n;i++)    //segmented sieve
        {
            int low=m/listofprime[i];
            low*=listofprime[i];
            for(int j=low+listofprime[i];j<=n;j+=listofprime[i])
                prime[j]=0;
        }
        for(int i=m;i<=n;i++)                   // print all prime numbers
        {
            if(prime[i]==1)
                printf("%d\n",i);
        }
        t-=1;
    }
}

LajosOnly (31)
I got no Compiler here, so maybe you can tell me what Errors and console Output you get.
MikeyBoy (5631)
What does "not working" mean? Can you give us a clear, complete and precise description of what the problem is?
closed account (1vf9z8AR)
I don't get any error. But it gives wrong output or no output at all.

Input is of the form-

number of test cases
range(two numbers separated by whitespace)

For example, for range 1 to 10, it only gives 5 and 7
For 1 to 100, no output.
LajosOnly (31)
1
2
3
4
5
 
for(int i=m;i<=n;i++)                   // print all prime numbers
        {
            if(prime[i]==1)
                printf("%d\n",i);
        }


Your first mistake you print only numbers of Array from Position 1 to 10, you should print from "m-1".

Afterwards you should make your Arrays as big as n but Change your for Loops to i < n not i <= n.

LajosOnly (31)
Here i got a example, how you can easily ask for primes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
 #include<stdio.h>
int main()
{
    int t,m,n;
    scanf("%d",&t);             // number of test cases
    while(t>0)
    {
        scanf("%d%d",&m,&n);
        int prime[n];           // for finding prime numbers
        int listofprime[n];     // for storing only prime numbers
        int pos=0;
        prime[0] = 0;
        prime[1] = 0;
        for(int i=2;i<n;i++)    
            prime[i]=i;
        for(int i = 2; i < n; i++)
        {
            if(prime[i] != 2 && prime[i]%2 == 0)
                prime[i] = 0;
            if(prime[i] != 3 && prime[i]%3 == 0)
                prime[i] = 0;
            if(prime[i] != 5 && prime[i]%5 == 0)
                prime[i] = 0;
            if(prime[i] != 7 && prime[i]%7 == 0)
                prime[i] = 0;
            if(prime[i] != 11 && prime[i]%11 == 0)
                prime[i] = 0;
        }
        for(int i=m-1;i<n;i++)                   // print all prime numbers
        {
            if(prime[i]!=0)
                printf("%d\n",i);
        }
        t-=1;
    }
}
Last edited on
tpb (1495)
I hope that's a joke.
LajosOnly (31)
Thats very helpful, thank you for your opinion and have a nice day
lastchance (6980)
@suyashsing234
Remove lines 26 to 32 in your last code (the "segmented sieve" bit) and it will work. No idea what you are doing here: I suspect you are trying to do (wrongly) what you are already doing on lines 22 and 23. Your sieve has already correctly set up the array prime[] and I don't see why you now intend to change it.

Line 9 is illegal in standard c++, though.
Last edited on
Thomas1965 (4571)
Line 9 is illegal in standard c++, though.

@lastchance,
he is using C and in C99 it's valid.
closed account (1vf9z8AR)
@lastchance
It works but this has become simple sieve and I want to make segmented sieve.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
 #include<stdio.h>
int main()
{
    int t,m,n;
    scanf("%d",&t);             // number of test cases
    while(t>0)
    {
        scanf("%d%d",&m,&n);
        int prime[n+1];           // for finding prime numbers
        int listofprime[n+1];     // for storing only prime numbers
        int pos=0;
        for(int i=2;i<=n;i++)     //declare all to 1
            prime[i]=1;
        prime[0]=0;
        prime[1]=0;
        for(int i=2;i<=n/i;i++)           //simple sieve
        {
            if(prime[i]==1)
            {
                listofprime[pos]=i;
                pos++;
                for(int mult=2;i*mult<=n;mult++)
                    prime[i*mult]=0;
            }
        }

        for(int i=m;i<=n;i++)                   // print all prime numbers
        {
            if(prime[i]==1)
                printf("%d\n",i);
        }
        t-=1;
    }
}
Last edited on
closed account (1vf9z8AR)
Here I wrote a new code to implement segmented sieve.

Thankfully it gives output but it's all wrong.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
#include<stdio.h>
#include<math.h>
int main()
{
    int testcases,lowerlimit,upperlimit;
    scanf("%d",&testcases);
    while(testcases>0)
    {
        scanf("%d%d",&lowerlimit,&upperlimit);
        int prime[upperlimit+1];
        int storeprime[upperlimit+1];
        int pos=0;

        for(int i=2;i<=upperlimit;i++)   //declare all to 1
            prime[i]==1;
        prime[0]=0;
        prime[1]=0;

        int upper1=sqrt(sqrt(upperlimit));
        int upper2=sqrt(upperlimit);

        for(int i=2;i<=upper1;i++)     //sieve to find primes till sqrt(n)
        {
            if(prime[i]==1)
            {
                storeprime[pos]=i;
                pos++;
                for(int mult=2;i*mult<=upper2;mult++)
                    prime[i]=0;
            }
        }

        for(int i=0;i<=pos-1;i++)    //segmented sieve
        {
            int low=lowerlimit/storeprime[i];
            low*=storeprime[i];
            for(int j=low;j<=upperlimit;j+=storeprime[i])
            {
                if(j!=storeprime[i])
                    prime[i]=0;
            }
        }

        for(int i=lowerlimit;i<=upperlimit;i++) //print all prime numbers
        {
            if(prime[i]==1)
                printf("%d\n",i);
        }

        testcases--;
    }
}

Last edited on
LajosOnly (31)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include<stdio.h>
#include<math.h>
int main()
{
    int testcases,lowerlimit,upperlimit;
    scanf("%d",&testcases);
    while(testcases>0)
    {
        scanf("%d%d",&lowerlimit,&upperlimit);
        int prime[upperlimit];
        int storeprime[upperlimit];
        int pos=0;

        for(int i=0;i<upperlimit;i++)   //declare all to 1
            prime[i]=1;
        prime[0]=0;
        prime[1]=0;

        //int upper1=sqrt(sqrt(upperlimit));
        //int upper2=sqrt(upperlimit);

        for(int i=2;i<=upperlimit/i;i++)     //sieve to find primes till sqrt(n)
        {
            if(prime[i]==1)
            {
                storeprime[pos]=i;
                pos++;
                for(int mult=2;i*mult<=upperlimit;mult++)
                    prime[i*mult]=0;
            }
        }

        for(int i=0;i<pos-1;i++)    //segmented sieve
        {
            int low=lowerlimit/storeprime[i];
            low*=storeprime[i];
            for(int j=low;j<upperlimit;j+=storeprime[i])
            {
                if(j==storeprime[i])
                    prime[i]=0;
            }
        }
        
        for(int i=lowerlimit-1;i<upperlimit;i++) //print all prime numbers
        {
            if(prime[i]==1)
                printf("%d\n",i);
        }

        testcases--;
    }
}
MikeyBoy (5631)
suyashsing234 wrote:
it's all wrong

You know when I said above:

MikeyBoy wrote:
Can you give us a clear, complete and precise description of what the problem is?

You really didn't learn anything at all from that, did you?
Last edited on
tpb (1495)
It's not really a segmented sieve since it only has one "segment".
Topic archived. No new replies allowed.