## Wednesday, March 18, 2015

### 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;
}

int size = ( max % 2 == 0 ? max/2 : (max/2)+1 );
int[] nums = new int[size];
nums = 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);
} catch (NumberFormatException nfe) {
System.out.println(args + " 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