WAP for Prime No..Checking & Generation in any range say n

bool is_prime(int x)
{
if(x <= 1)
return false;
for(int i = 2; i < x; i++)
if(x%i == 0)
return false;
return true;
}

This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,


bool is_prime(int x)
{
if(x <= 1)
return false;
for(int i = 2; i <= x/2; i++)
if(x%i == 0)
return false;
return true;
}

But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.

Hence the best approach to check if a number is prime or not will be


bool is_prime(int x)
{
if(x <= 1)
return false;
int s = (int) sqrt(x);
for(int i = 2; i <= s; i++)
if(x%i == 0)
return false;
return true;
}


Generate Prime Number in A Range

/* Generate a prime list from 0 up to n, using The Sieve of Erantosthenes
param n The upper bound of the prime list (including n)
param prime[] An array of truth value whether a number is prime
*/
void prime_sieve(int n, bool prime[]) {
prime[0] = false;
prime[1] = false;
int i;
for (i = 2; i <= n; i++)
prime[i] = true;

int limit = sqrt(n);
for (i = 2; i <= limit; i++) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i)
prime[j] = false;
}
}
}

Java Program //Working


public class prime_sieve
{


public static void main(String a[])
{

runEratosthenesSieve(100);

}

public static void runEratosthenesSieve(int upperBound) {

int upperBoundSquareRoot = (int) Math.sqrt(upperBound);

boolean[] isComposite = new boolean[upperBound + 1];

for (int m = 2; m <= upperBoundSquareRoot; m++) {

if (!isComposite[m]) {

System.out.print(m + " ");

for (int k = m * m; k <= upperBound; k += m)

isComposite[k] = true;

}

}

for (int m = upperBoundSquareRoot; m <= upperBound; m++)

if (!isComposite[m])

System.out.print(m + " ");

}


}