The problem of listing prime numbers is nice. It is a simply understood problem which has been gradually understood better over 3000 years of effort. It emphasizes that domain knowledge pushes better algorithms. There is a current discussion of this problem here, at ulam's spiral too slow.