1 / 7
Oct 2020

The code runs fine on terminal, but on submission it gives NZEC error.

The problem link: PRIME1

Full code:(using segmented sieve)

import java.util.*;
class primes
{
	public static void main (String args[])
	{
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();

		while(t-- >0)
		{
			int low = sc.nextInt();
			int high = sc.nextInt();

			segmentedSieve(low,high);
		}
	}

	static void segmentedSieve(int low, int high)
	{
		Vector<Integer> p = new Vector<Integer>();
		sieve(high, p);

		boolean[] mark = new boolean[high-low+1];
		for(int i = 0;i<mark.length;i++)
			mark[i]=true;

		for(int i=0;i<p.size();i++)
		{

			int lowest = (low/p.get(i)) * p.get(i);
			lowest+=p.get(i);

			for(int j=lowest;j<=high;j=j+p.get(i))
			{
				if(j!=p.get(i))
					mark[j-low] = false;
			}
		}

		for(int i=low;i<=high;i++)
		{
			if(mark[i-low]==true)
				System.out.println(i);
		}System.out.println();
		//line change
	}

	static void sieve(int n, Vector<Integer> prime)
	{

		boolean[] primes = new boolean[n+1];
		for(int i = 0;i<=n;i++)
			primes[i] = true;

		for(int i = 2;i*i<=n; i++)
		{
			if(primes[i] == true)
			{
				for(int j = i*i;j<=n;j=j+i)
					primes[j]=false;
			}
		}

		for(int i = 2; i <= n; i++) 
        { 
            if(primes[i] == true)
                prime.add(i);
        } 
	}
}
  • created

    Oct '20
  • last reply

    Oct '20
  • 6

    replies

  • 664

    views

  • 2

    users

  • 2

    links

Does it run fine with this test case?

1
999999900 1000000000

Nope, it threw an exception:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at primes.sieve(primes.java:59)
	at primes.segmentedSieve(primes.java:26)
	at primes.main(primes.java:15)

The best strategy I came up with to solve this problem was segmented sieve, which doesn’t seem to work.

Any suggestions on how to solve this one?

Similar questions have been asked many times before. You’ll find some ideas if you search the forum5.

Thanks for your help, the issue was in the simple sieve function, the boolean array needed to be of size sqrt(upperlimit)

It is solved now :slight_smile: