08 January 2009

Finding composites

Another brain-teaser for Jeff and Jefrrey that I missed while my subscription was interrupted: Andrew Koenig reintroduces the 2-3-5 problem, attributed to Dijkstra and Hamming:
Write a program that produces, in ascending order, the sequence of positive integers that have only 2, 3, and 5 as their prime factors. The first such integer is 1 (which has no prime factors at all; hence all of its prime factors are either 2, 3, or 5); the sequence continues with 2, 3, 4 (which has only 2 as a prime factor), 5, and 6. It skips 7, which is prime, continues with 8, 9, and 10, skips 11, includes 12, and so on.

No comments: