In arithmetic, an n-smooth number, where n is a given prime number, is mathematically defined as a positive integer that has no prime factors greater than n. For example, 42 is 7-smooth because all its prime factors are less than or equal to 7, but 44 is not 7-smooth because it also has 11 as a prime factor.
Define a pretty smooth number as a number with no prime factors greater than its own square root. Thus, the list of pretty smooth numbers can be formulated as follows:
- (EDITED!) 1 is a pretty smooth number, due to its complete lack of any prime factors. (Note that in the original version of this question, 1 was erroneously excluded from the list, so if you exclude it from your outputs you won't be marked wrong.)
- Between 4 (= 22) and 8, the pretty smooth numbers are 2-smooth, meaning they have 2 as their only prime factor.
- Between 9 (= 32) and 24, the pretty smooth numbers are 3-smooth, and can have 2s and 3s in their prime factorizations.
- Between 25 (= 52) and 48, the pretty smooth numbers are 5-smooth, and can have 2s, 3s, and 5s in their prime factorizations.
- And so on, upgrading the criteria every time the square of the next prime number is reached.
The list of pretty smooth numbers is fixed, and begins as follows: 1, 4, 8, 9, 12, 16, 18, 24, 25, ...
Your challenge is to write code that will output all pretty smooth numbers up to and including 10,000 (= 1002). There must be at least one separator (it doesn't matter what kind -- space, comma, newline, anything) between each number in the list and the next, but it is completely irrelevant what character is used.
As per usual, lowest byte count wins -- obviously, simply outputting the list isn't going to be too beneficial to you here. Good luck!