Segmented sieve

closed account (1vf9z8AR)
My segmented sieve is not outputting as expected. I am not able to figure out what is the issue.

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
  #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;
    }
}
What does it do that you don't expect? What does it not do that you expected it would do?

Looks like you sometimes use == where you mean =.
Last edited on
closed account (1vf9z8AR)
Here i changed my code a bit. But still issue with output. For range 1 to 10 it gives only 5 and 7 , for 1 to 100 no output.
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
 #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;
    }
}
Topic archived. No new replies allowed.