prime generator

general
1

prime generator with less complexity and less memory

In this problem you have to print all primes from given interval.

Input
t - the number of test cases, then t lines follows. [t <= 150]
On each line are written two integers L and U separated by a blank. L - lower bound of interval, U - upper bound of interval, [2 <= L < U <= 2147483647] [U-L <= 1000000].

Output
For each test case output must contain all primes from interval [L; U] in increasing order.

Example
Input:
2
2 10
3 7

Output:
2
3
5
7
3
5
7

1 Like
2

There is such problem on CodeChef - PRIME1. You can see all submissions here :wink:

1 Like
3

All the solutions in that set are using more memory

4

use AKS_primality algorithm for best and most famous result. Invented by Prof. Aggrawal and his students Kayal and Saxena of IIT Kanpur, in March 2003 and modified and improved subsequntly.

2 Likes
5

import java.util.*;
class p
{
public static boolean isprime(int n)
{int i,o;
if(n<=1)
return false;
if(n==2)
return true;
if(n%2==0)
return false;
double e = Math.sqrt(n);
o = (int)e;
for(i=3;i<=o;i++)
{
if(n%i==0)
return false;
}
return true;
}
}
class pg
{
public static void main(String args[])
{
Scanner s = new Scanner(System.in);
int t,n,x,a[],i,j,r,y;
double g;
t = s.nextInt();
while(true)
{
t–;
x = s.nextInt();
y = s.nextInt();
a = new int[y+1];
for(i=x;i<=y;i++)
a[i]=i;
g = Math.sqrt(y);
r = (int)g;

			for(i=2;i<=r;i++)
				if(p.isprime(i))
				{//System.out.println("i  m prime"+a[i]);
				for(j=i*2;j<=y;j=j+i)
				a[j]=0;
				}
				else 
				a[i]=0;
			for(i=x;i<=y;i++)
				if(a[i]!=0&&i!=1)
				System.out.println(a[i]);
			System.out.println();
			if(t==0)
			break;
			}
		}
	}

someone plz help me…i m getting nzec error for this code…

6

i didn’t get what modifications u had done…can u plz elaborate it would be a great help…

7

if you are asking me, I just formatted your post…

8

the error is becoz of array out of bound…
you are making the index of a[] zero which are even less than x.
so first check before the 44th line whether the value of j is >= to x.

9

error i m getting is :Exception in thread “main” java.lang.OutOfMemoryError: Java heap space
at pge.main(pge.java:35)…

10

can you give the link??

1 Like