Segmented Sieve of Eratosthenes - Java

Question

So I was trying to implement Segmented Sieve of Eratosthenes in Java and this is the best I could do. When I run it, it gives no errors but it doesn't return anything, despite me added "System.out.println" at the end to print out all the remaining primes. Thanks in advance for the recommendations

public class SegmentedSieveofEratosthenes  {

public static void main(String[] args) throws java.lang.Exception {
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int m = in.nextInt();
    boolean[] v = new boolean[1000000];
    int[] primes = new int[1000000];
    //counter for the primes vector
    int counter = 0;

    for(int i=2;i<=(int)Math.sqrt(m);i++)
    {
        v[i]=true;
    }

    for(int i=2;i<=(int)Math.sqrt(m);i++)
    {
        if(v[i]=true)
        {
            primes[counter]=i;
            counter=counter+1;
            for(int j=i+1;j<=(int)Math.sqrt(m);j++)
            {
                if(j%i==0)
                {
                    v[j]=false;
                }
            }
        }
    }

    boolean[] flags = new boolean[1000000];
    for(int i=n;i<=m;i++)
    {
        flags[i]=true;
    }

    for(int i=0;i<counter;i++)
    {
        int start = (n/primes[i])*3;
        for(int j=start+i;j<=m;j=j+i)
            flags[j]=false;
    }

    for(int i=n;i<=m;i++)
        if(flags[i]==true)
            System.out.println(i);

    in.close();
    }
  }

Just a comment: choose a curly brace style. The communities of same line curly and next line curly don't get along. This style of using both will create a war the likes of which you have never seen. — Paul Nikonowicz

Dillon Davis Dillon Davis · Accepted Answer · 2019-01-06T22:56:03

There were three distinct problems with your implementation. The first issue was that you were assigning v[i] to true in a condition

if(v[i]=true)

Then there were a few off-by-one errors in the termination condition of the for loops, specifically

for (...; i<=m; ...)

instead of

for (...; i<m; ...)

And then lastly, something was off in your math for the the following

int start = (n/primes[i])*3;
for(int j=start+i;j<=m;j=j+i)
    flags[j]=false;

I'm sure it was a small fix, but I couldn't figure it out so I just wrote my own

int start = n + (-n % primes[i]);
for(int j=start;j<m;j+=primes[i])
    flags[j]=false;

Additionally, I made a few small changes to your sieve to speed things up. Rather than checking every number following a prime modulo said prime, I start at prime^2 (where ^ denotes exponentiation) and increment by prime, only flagging multiples with no wasted checks.

Original

primes[counter]=i;
counter=counter+1;
for(int j=i+1;j<=(int)Math.sqrt(m);j++)
{
    if(j%i==0)
    {
        v[j]=false;
    }
}

Optimized

primes[counter++]=i;
for(int j=i*i;j<=(int)Math.sqrt(m);j+=i)
{
    v[j]=false;
}

Put together-

import java.util.Scanner;
import java.util.Arrays;
public class SegmentedSieveofEratosthenes  {

    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int m = in.nextInt();
        boolean[] v = new boolean[1000000];
        int[] primes = new int[1000000];
        //counter for the primes vector
        int counter = 0;

        for(int i=2;i<=(int)Math.sqrt(m);i++)
        {
            v[i]=true;
        }

        for(int i=2;i<=(int)Math.sqrt(m);i++)
        {
            if(v[i])
            {
                primes[counter++]=i;
                for(int j=i*i;j<=(int)Math.sqrt(m);j+=i)
                {
                    v[j]=false;
                }
            }
        }

        boolean[] flags = new boolean[1000000];
        for(int i=n;i<m;i++)
        {
            flags[i]=true;
        }

        for(int i=0;i<counter;i++)
        {
            int start = n + (-n % primes[i]);
            for(int j=start;j<m;j+=primes[i])
                if (j != primes[i])
                    flags[j]=false;
        }

        for(int i=n;i<m;i++)
            if(flags[i])
                System.out.println(i);

        in.close();
    }
}

Output for n = 800 and m == 1000 for example

Segmented Sieve of Eratosthenes - Java

2 Answers