# prime generator

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

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

1 Like

All the solutions in that set are using more memory

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

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…

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