Note: Version 2, below, uses the Sieve of Eratosthenes. There are several answers that helped with what I originally asked. I have chosen the Sieve of Eratosthenes method, implemented it, and changed the question title and tags appropriately. Thanks to everyone who helped!
I wrote this fancy little method that generates an array of int containing the prime numbers less than the specified upper bound. It works very well, but I have a concern.
private static int [] generatePrimes(int max) { int [] temp = new int [max]; temp [0] = 2; int index = 1; int prime = 1; boolean isPrime = false; while((prime += 2) <= max) { isPrime = true; for(int i = 0; i < index; i++) { if(prime % temp [i] == 0) { isPrime = false; break; } } if(isPrime) { temp [index++] = prime; } } int [] primes = new int [index]; while(--index >= 0) { primes [index] = temp [index]; } return primes; }
My concern is that I am creating an array that is far too large for the final number of elements the method will return. The trouble is that I don't know of a good way to correctly guess the number of prime numbers less than a specified number.
This is how the program uses the arrays. This is what I want to improve upon.
temp[]
that has nonzero elements to primes[]
without having to iterate through both arrays and copy the elements one by one?Version 2 (thanks to Jon Skeet):
private static int [] generatePrimes(int max) { int [] temp = new int [max]; temp [0] = 2; int index = 1; int prime = 1; boolean isPrime = false; while((prime += 2) <= max) { isPrime = true; for(int i = 0; i < index; i++) { if(prime % temp [i] == 0) { isPrime = false; break; } } if(isPrime) { temp [index++] = prime; } } return Arrays.copyOfRange(temp, 0, index); }
Version 3 (thanks to Paul Tomblin) which uses the Sieve of Erastosthenes:
private static int [] generatePrimes(int max) { boolean[] isComposite = new boolean[max + 1]; for (int i = 2; i * i <= max; i++) { if (!isComposite [i]) { for (int j = i; i * j <= max; j++) { isComposite [i*j] = true; } } } int numPrimes = 0; for (int i = 2; i <= max; i++) { if (!isComposite [i]) numPrimes++; } int [] primes = new int [numPrimes]; int index = 0; for (int i = 2; i <= max; i++) { if (!isComposite [i]) primes [index++] = i; } return primes; }
Your method of finding primes, by comparing every single element of the array with every possible factor is hideously inefficient. You can improve it immensely by doing a Sieve of Eratosthenes over the entire array at once. Besides doing far fewer comparisons, it also uses addition rather than division. Division is way slower.
ArrayList<>
Sieve of Eratosthenes// Return primes less than limit static ArrayList<Integer> generatePrimes(int limit) { final int numPrimes = countPrimesUpperBound(limit); ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes); boolean [] isComposite = new boolean [limit]; // all false final int sqrtLimit = (int)Math.sqrt(limit); // floor for (int i = 2; i <= sqrtLimit; i++) { if (!isComposite [i]) { primes.add(i); for (int j = i*i; j < limit; j += i) // `j+=i` can overflow isComposite [j] = true; } } for (int i = sqrtLimit + 1; i < limit; i++) if (!isComposite [i]) primes.add(i); return primes; }
Formula for upper bound of number of primes less than or equal to max
(see wolfram.com):
static int countPrimesUpperBound(int max) { return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0; }
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With