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 |

## No comments:

## Post a Comment