0

Is there any fast approach to get all divisors of an integer by only using pen & paper?

muffel
  • 2,879
  • Probably one of the quickest ways is to attempt to divide by all possible small primes to get the prime factorization. Once you have the prime factorization, finding all the other divisors is trivial. – Peter Woolfitt Jul 06 '14 at 08:10
  • 2
    Not if the integer is too big to fit on your paper! – Alex Kruckman Jul 06 '14 at 08:11
  • @PeterWoolfitt How do I get from the divisors to the prime factors? – muffel Jul 06 '14 at 08:44
  • 1
    I was saying that it is easy to get from the prime factorization to the divisors. Suppose that $n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$ where each $p_i$ is a distinct prime and $k_i$ is a positive integer. Then each divisor can be written as $p_1^{j_1}p_2^{j_2}\cdots p_m^{j_m}$ where $0\le j_i\le k_i$, and all possible numbers of this form are divisors. – Peter Woolfitt Jul 06 '14 at 08:57

1 Answers1

1

The shortest approach would be to get a rough idea of the squareroot of the integer and then try dividing by all prime numbers starting from least upto that number.

Additional advice, try getting an intuition from the last digits to avoid any unnecessary divisions, for e.g.all multiples of 5 end with $0/5$.

RE60K
  • 17,716