Problem: Given some integer N, find first N prime numbers.
Solution: Prime number is one which is divisible only by itself or by 1.
First few prime numbers are 2, 3, 5, 7, 11, 13, 17 and so on.
import java.util.ArrayList;
import java.util.List;
public class PrimeNumbers
{
// basic function to check if a given integer is prime or not
static boolean checkPrime(int i)
{
int j=2;
while (j<i)
{
if (i%j==0)
return false;
j++;
// if j has been incremented till square-root(i), then look no further
if (i/j < j)
break;
}
return true;
}
// optimization over the above function
// An integer is checked for primeness given all the primes below that number.
// It is more efficient, because it does not check division by prime-multiples (example:4) if
// we have already checked division by primes (example: 2)
static boolean checkPrime(int i, List<Integer> primes)
{
for (int j : primes)
if (i%j==0)
return false;
return true;
}
// Driver function to test the above functions
public static void main(String[] args)
{
List <Integer> primes = new ArrayList<Integer> ();
primes.add(2);
int i=3;
while (primes.size() < 100)
{
// determine prime division by efficient function
if (checkPrime(i, primes))
{
primes.add(i);
// test if the first implementation of prime function also returns the same
System.out.println (i + " = " + checkPrime(i) + ", " + (i+2) + " = " + checkPrime(i+2));
}
i=i+2;
}
}
}
