So the time for this to have been a homework assignment has passed, right?

The proposed algorithm is very much like the one I used back at college, quite a long time ago. That program was in PDP10 assembler, and ran until the 512k address space of 36bit data was filled up… In general, you don’t get to tell if the result of a division is floating point or not; you either divide by an integer and get a quotient (and usually a remainder), or you use floating point for both numbers and hope you get nice even numbers when you divide numbers. Most prime calculators will use integers.

Here’s my modern effort. It adds to the original algorithm presented (and to the one I did in college), in that it notices that you can test many numbers for primeness even after the array you can save primes in has become full. You can test primes up to the square of your largest prime…

This code find all the 16 bit primes in about 7 seconds. printing them out increase that to about 16 seconds (there’s a lesson there…)

```
/*
* Calculate primes, minimizing memory use for microcontrollers.
* By William Westfield (WestfW), Jan 2010.
*/
#define ARDUINO 1 // lets run on an arduino; a tiny microcontroller board.
/*
* We test primes by seeing whether they're divisible by previously
* found primes. We have limited memory to remember those primes, though.
* MAXPRIMES is the number we have room for (a guess...)
*/
#define MAXPRIMES 256
unsigned short primes[MAXPRIMES];
unsigned short lastprime;
typedef unsigned char boolean;
#define TRUE 1
#define FALSE 0
#define MAXUSHORT 0xFFFF
boolean done;
#if ARDUINO
#define printprime(d) Serial.println(d);
#define printstring(s) Serial.println(s);
#else
#include <stdio.h>
#define printprime(d) printf("%d\n", d);
#define printstring(s) printf("%s\n", s);
#endif
/*
* test if a number is prime by seeing if it is evenly divisible
* by any of the primes we've already found.
*/
boolean testprime (unsigned short t)
{
int i;
unsigned int p; // prime to test with
for (i=0; i < MAXPRIMES; i++) {
p = primes[i];
if (p == 0) {
return TRUE; // indivisible by all primes so far
}
if ((long)p*(long)p > (long)t) {
return TRUE; // indivisible by primes up to sqrt(t)
}
if ((t % p) == 0) {
return FALSE; // divisible by this factor!
}
} // If this exits, it means we got the end of MAXPRIMES
printstring("Primes exceed testability at pp, tp, i== ");
printprime(t);
printprime(p);
printprime(i);
done = TRUE;
return FALSE;
}
#if ARDUINO
void setup()
{
Serial.begin(57600);
}
void loop()
#else
int main()
#endif
{
unsigned short pp; /* our possible primt */
done = FALSE;
lastprime = 0;
printprime(2); /* 2 is a special case! */
for (pp = 3; !done; pp += 2) {
if (testprime(pp)) {
if (lastprime < MAXPRIMES) {
/*
* We can go on testing primes even after we can't save them
* as long as the number being tested is less than the square
* of the last prime we've found.
*/
primes[lastprime++] = pp;
if (lastprime >= MAXPRIMES) {
printstring("saved prime array full at pp=");
printprime(pp);
}
}
printprime(pp);
}
if (pp == MAXUSHORT) {
break;
}
}
#if ARDUINO
printstring("Finished at time ");
Serial.print(millis());
while (1) ; // stop !
#else
return (0);
#endif
}
```