🕰️
Factors
Week 12
In mathematics, culture and religion, the number 12 often appears significant - for example:
- It has more factors than any smaller number
- It's semiprime
- 12 hours in a clock and 12 months in a year
- 12 inches in a foot
- Dozens were often used for quantities/trade
- 12 zodiac signs, apostles, Imams, tribes of Israel etc
For this challenge, we want to order the integers 1 to 100,000 by number of factors - if two numbers have the same number of factors (e.g. 6, 8 and 10 all have 4 factors), then the smaller number should be displayed first
When the factor count changes, there should be an empty line to easily visually-separate the groups - e.g. in the example program output for the first 10 numbers, you can see that 6, 8 and 10 have 4 factors, 4 and 9 have 3 factors, 2, 3, 5, 7 have 2 factors and 1 has 1 factor
Below shows the program output for the first 10 numbers in the format number : number of primes
Your program should produce output in the same format for each integer in the range 1 to 100,000
Hints
Hints will be released at the start of each of the following days - e.g. the start of day 3 is 48 hours after the challenge starts
| Release Day | Hint |
|---|---|
| 2 | There are multiple ways to check if a number can be divided by another - a good approach is usually to check if the number has 0 remainder once divided by the other using the modulus operator |
| 3 | You know a number can always be divided by 1 and itself, so can skip could start the factor count accordingly (think what the factor count should start at for 1 vs all other positive integers) |
| 5 | A slow, but working approach is to loop through every number between 1 and itself (or from 2 to n - 1 if you have already started the counter with the factors of 1 and itself already accounted for) and increment the counter if the result of the modulo division is 0 |
| 6 | A more efficient approach is to loop up to only the floor square root of the number - e.g. for 20, we'd only need to loop up to 4 - this is since 20 / 4 = 5 and 20 / 5 = 4 - since both 4 and 5 are factors, we don't have to check both. We could simply increase the count by 2 when we find the lower factor pair - consider what should happen with a square number, when we do 9 / 3 = 3 for example |