A long time ago in a galaxy far, far away (okay maybe like 22 years ago in Port Royal, Pennsylvania) I did a comic about a frog that ran weekly in a local newspaper. At one comic per week, it took me nearly 2 years to reach 100. I guess it's really not that impressive, since Garfield reached 100 comics published in under 17 weeks.
But you know what I don't like about the number 100? It's not prime. 101 is though. If you ever want to calculate a list of prime numbers, you can use the Sieve of Eratosthenes. It is a very efficient algorithm for finding "smaller" primes (the primes that normal people would want, if normal people want primes at all). I implemented it once in Java.
public class SieveOfEratosthenes {
/**
* Uses the Sieve of Eratosthenes to calculate an array of prime
* numbers up to a given maximum number.
*
* @param max the highest number to consider for primeness
* @return an array containing prime numbers
*/
private static int[] getPrimes(int max) {
if (max < 2) {
return new int[0];
}
int size = ( max % 2 == 0 ? max/2 : (max/2)+1 );
int[] nums = new int[size];
nums[0] = 2; // 2 is the first prime and only even prime
// we'll fill the rest of the array with the odds,
// since we know that all the evens will just be removed anyway
int n = 3;
for (int i = 1; i < nums.length; i++) {
nums[i] = n;
n = n + 2;
}
// we can stop when we get past the square root of max
int sqRoot = (int) Math.sqrt(max);
int idx = 0;
int f = nums[idx];
while (f <= sqRoot) {
if (f != -1) {
// "remove" all numbers that are multiples of f.
// basically that just means set them to -1 and
// ignore them in the future.
for (int j = idx+1; j < nums.length; j++) {
int num = nums[j];
if (num != -1) {
if (num % f == 0) {
nums[j] = -1;
}
}
}
}
f = nums[idx++];
}
// clean up the list (remove the -1's)
int marker = 0;
int index = 0;
int lastPrimeIndex = 0;
while (index < nums.length) {
if (nums[index] != -1) {
lastPrimeIndex = marker;
marker++;
} else {
for (int k = marker; k < nums.length; k++) {
if (nums[k] != -1) {
nums[index] = nums[k];
nums[k] = -1;
if (index > lastPrimeIndex) {
lastPrimeIndex = index;
}
marker = k+1;
break;
}
}
}
index++;
}
int[] ret = new int[lastPrimeIndex+1];
System.arraycopy(nums, 0, ret, 0, lastPrimeIndex+1);
return ret;
}
public static void main(String[] args) {
if (args.length < 1) {
System.out.println("no arguments given");
System.exit(1);
} else {
int largest = 0;
try {
largest = Integer.parseInt(args[0]);
} catch (NumberFormatException nfe) {
System.out.println(args[0] + " is not an integer");
System.exit(1);
}
int[] primes = getPrimes(largest);
// print out the list
for (int i = 0; i < primes.length; i++) {
if (i > 0) {
System.out.print(',');
}
System.out.print(primes[i]);
}
}
}
}
Give that class a command-line argument of an integer and it will return you a list of prime numbers up to and including that number. I'll warn you though, very large numbers will take a while to calculate.
Today's comic includes multiple references to the number 100, which is a fine number to use as input to the sieve.
 |
| Amphibian.com comic for 18 March 2015 |
