E228

How's that for the shortest title ever? How can you decide if a number is the sum of two squares? Euler begins with the dumbest possible algorithm you can think of: Take the number, subtract a square, and check if the remainder is a square. If not, repeat, repeat, repeat. But Euler, being Euler, finds a way of converting all those subtractions into additions. He applies this to 1,000,009, and---in less than a page---finds that there are two ways to express this as a sum of squares. Hence, by earlier work in E228, it is not a prime. Amusingly, when he later described how to prepare a table of primes ``ad millionem et ultra'' (E467), he includes this number as prime. So he then feels obliged to write another paper, E699, using another refinement of his method, to show that 1,000,009 is not prime.