Find the Smallest N Prime Numbers in Ascending Order
Lydia Yuan
Posted on April 8, 2023
The Question
Please implement a function that, given an integer parameter N, can print the smallest N prime numbers in ascending order, for example, when N = 10, print 2 3 5 7 11 13 17 19 23 29.
The Most Basic Trail Division
public static boolean isPrime(int n) {
if (n <= 1 || n % 2 == 0) {
return false;
}
for (int i = 3; i <= Math.sqrt(n); i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static void printFirstNPrimeNumbers(int N) {
if (N == 0) {
return;
}
System.out.println(2);
int printedCount = 1;
int current = 3;
while (printedCount < N) {
if (isPrime(current)) {
printedCount++;
System.out.println(current);
}
current++;
}
}
Less Checks & Cache Time Space Tradeoff
A better way to judge if a number is a prime number is to check if it can be divided by a prime number. Rather than checking all odd numbers until the square root of the given number, we can check only prime numbers until the square root of the given number. This is because if a number is not divisible by 2, it is also not divisible by any other even number. Similarly, if a number is not divisible by 3, it is also not divisible by any multiple of 3, such as 9. Therefore, we can improve the performance of our prime number check by caching all the encountered prime numbers and only checking division by these prime numbers up to the square root of the given number. This reduces the number of division checks required, which can be a significant optimization for large numbers.
public static boolean isPrime(int n, Set<Integer> encounteredPrimeNumbers) {
if (encounteredPrimeNumbers.contains(n)) {
return true;
}
if (n <= 1 || n % 2 == 0) {
return false;
}
for (int primeNumber : encounteredPrimeNumbers) {
if (n % primeNumber == 0) {
return false;
}
}
encounteredPrimeNumbers.add(n);
return true;
}
public static void printFirstNPrimeNumbers(int N) {
if (N == 0) {
return;
}
Set<Integer> encounteredPrimeNumbers = new LinkedHashSet<>();
encounteredPrimeNumbers.add(2);
System.out.println(2);
int printedCount = 1;
int current = 3;
while (printedCount < N) {
if (isPrime(current, encounteredPrimeNumbers)) {
printedCount++;
System.out.println(current);
}
current++;
}
}
Sieve of Eratosthenes
For a visual demonstration of the Sieve of Eratosthenes algorithm, be sure to check out the animated gif on the Wikipedia page. It can help give you a better intuition for how the sieve method works and how it is used to find prime numbers.
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
Implementing the Sieve of Eratosthenes method requires a boolean array to mark whether a number is prime or not. Additionally, we need to estimate the number of candidate numbers we need to examine to find the first N prime numbers. To do so, we can use prime counting functions. However, the distribution of primes is not uniform, and there may be potential gaps in our range. A good rule of thumb is to expand the range by about 10-20% of the target value of N. I would be conservative and choose the 20% expansion here to go with the most simple prime counting function x / ln(x).
In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by π(x) (unrelated to the number π).
public static int getEstimatedUpperBound(int N) {
// binary search
// Prime-counting function with 20% expansion : x / ln(x) > N * 1.2
int lo = 1;
int hi = Integer.MAX_VALUE;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
double val = mid / Math.log(mid);
if (val > N * 1.2) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public static void printFirstNPrimeNumbers(int N) {
if (N == 0) {
return;
}
int estimatedUpperBound = getEstimatedUpperBound(N);
Boolean[] isComposite = new Boolean[estimatedUpperBound + 1];
Arrays.fill(isComposite, false);
int primeNumberCount = 0;
for (int i = 2; i <= isComposite.length && primeNumberCount < N; i++) {
if (!isComposite[i]) {
System.out.println(i);
primeNumberCount++;
for (int j = i * i; j < isComposite.length; j += i) {
isComposite[j] = true;
}
}
}
}
Use Bit Masking to Save More Space
Bitmasking is a space-efficient technique that can be used to represent boolean values. In the given code, a boolean array is used to mark composite numbers while finding the first N prime numbers. However, the size of the boolean array grows linearly with the size of the range of numbers being searched.
On the other hand, if we use a bitset, we can store each boolean value using just one bit, rather than a whole byte as with a boolean array. This means that we can store 8 boolean values in the space of a single byte, effectively reducing the memory consumption by a factor of 8. Thus, the bit masking method saves 8 times more space than the regular boolean array in this code.
public static void printFirstNPrimeNumbers(int N) {
if (N == 0) {
return;
}
int estimatedUpperBound = getEstimatedUpperBound(N);
int numInts = (estimatedUpperBound + 1 + 31) / 32;
// number of integers needed, rounded up to 32*n
int[] isComposite = new int[numInts];
int primeNumberCount = 0;
for (int i = 2; i <= estimatedUpperBound && primeNumberCount < N; i++) {
if ((isComposite[i / 32] & (1 << (i % 32))) == 0) {
System.out.println(i);
primeNumberCount++;
for (int j = i * i; j <= estimatedUpperBound; j += i) {
// mark all multiples of i as composite
isComposite[j / 32] |= (1 << (j % 32));
}
}
}
}
Posted on April 8, 2023
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
