100th Comic

Today I've published 100 comics since starting my Amphibian.com webcomics on August 1, 2014. I feel like that's a major accomplishment. At least it's a large number. Not large like the national debt of the United States or Apple's market capitalization or anything, but pretty big.

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