### Number Theory Questions - Factors

- How many numbers are there less than 100 that cannot be written as a multiple of a perfect square greater than 1?
- Find the smallest number that has exactly 18 factors?

To begin with, all prime numbers will be part of this list. There are 25 primes less than 100. (That is a nugget that can come in handy)

^{n}q cannot be a part of this list if n is greater than 1, as then the number will be a multiple of p

^{2}.

This is a brute-force question.

Post this, we need to count all numbers of the form p*q*r, where p, q, r are all prime.

We can list all multiples of perfect squares (without repeating any number) and subtract this from 99

16 - 0 new multiples

25 - 3 new multiples { 25, 50, 75

36 – 0 new ones

49 – 2 { 49, 98}

64 - 0

81 - 0

So, total multiples of perfect squares are 38. There are 99 numbers totally. So, there are 61 numbers that are not multiples of perfect squares

This is a difficult and time-consuming question. But a question that once solved, helps practice brute-force counting. Another takeaway is the fact that there are 25 primes less than 100. There is a function called pi(x) that gives the number of primes less than or equal to x. pi(10) = 4, pi(100) = 25

4. Find the smallest number that has exactly 18 factors?

Any number of the form p

^{a}q

^{b}r

^{c}will have (a+1) (b+1)(c+1) factors, where p, q, r are prime. (This is a very important idea)

^{a}q

^{b}, then it can be of the form

^{1}q

^{8}or p

^{2}q

^{5}

^{a}, then it can be of the form

^{17}

^{a}q

^{b}r

^{c}, then it can be of the form

^{1}q

^{1}r

^{2}

^{17}, p

^{2}q

^{5}, p

^{1}q

^{8}or p

^{1}q

^{2}r

^{2}

**prime factorizations that can result in a number having 18 factors.**

__only possible__^{17}- Smallest number = 2

^{17}

^{2}q

^{5 }– 3

^{2}* 2

^{5}

^{1}q

^{8}– 3

^{1}* 2

^{8}

^{1}q

^{1}r

^{2}– 5

^{1}* 3

^{1}* 2

^{2}

^{1}* 3

^{1}* 2

^{2}= 180

Labels: CAT number theory, CAT Solutions