krit.club logo

The World of Algorithms - Computing the Divisors of a Number

Grade 9CBSE

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

A divisor (or factor) of a natural number nn is an integer dd that divides nn without leaving a remainder. This is expressed as n(modd)=0n \pmod d = 0.

•

Every number n>1n > 1 has at least two divisors: 11 and nn itself.

•

Naive Algorithm: To find all divisors, we can iterate through every integer ii from 11 to nn. If nn is divisible by ii, then ii is a divisor. This algorithm takes nn steps (O(n)O(n) complexity).

•

Optimized Algorithm: Divisors always occur in pairs. If dd is a divisor of nn, then nd\frac{n}{d} is also a divisor. For any such pair (d,nd)(d, \frac{n}{d}), at least one of the divisors must be less than or equal to n\sqrt{n}.

•

By iterating only up to n\sqrt{n}, we can find all divisors efficiently. If ii is a divisor, we record both ii and n/in/i. If i=n/ii = n/i (which happens when nn is a perfect square), we count it only once.

•

The total number of divisors can be calculated using the prime factorization of the number. If n=p1a×p2b×p3cn = p_1^{a} \times p_2^{b} \times p_3^{c}, the number of divisors is (a+1)(b+1)(c+1)(a+1)(b+1)(c+1).

📐Formulae

n(modd)=0n \pmod d = 0

n=p1a1×p2a2×⋯×pkakn = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}

Total Number of Divisors=(a1+1)(a2+1)…(ak+1)\text{Total Number of Divisors} = (a_1 + 1)(a_2 + 1) \dots (a_k + 1)

💡Examples

Problem 1:

Using the optimized algorithm, find all the divisors of 4848.

Solution:

  1. Find the approximate value of 48\sqrt{48}. Since 62=366^2 = 36 and 72=497^2 = 49, 48≈6.92\sqrt{48} \approx 6.92.
  2. We check integers ii from 11 to 66:
  • i=1i = 1: 48÷1=4848 \div 1 = 48. Divisors: {1,48}\{1, 48\}
  • i=2i = 2: 48÷2=2448 \div 2 = 24. Divisors: {2,24}\{2, 24\}
  • i=3i = 3: 48÷3=1648 \div 3 = 16. Divisors: {3,16}\{3, 16\}
  • i=4i = 4: 48÷4=1248 \div 4 = 12. Divisors: {4,12}\{4, 12\}
  • i=5i = 5: 4848 is not divisible by 55.
  • i=6i = 6: 48÷6=848 \div 6 = 8. Divisors: {6,8}\{6, 8\}
  1. List all unique divisors in ascending order: {1,2,3,4,6,8,12,16,24,48}\{1, 2, 3, 4, 6, 8, 12, 16, 24, 48\}.

Explanation:

Instead of checking all 4848 numbers, we only needed to perform 66 divisions to find all 1010 divisors.

Problem 2:

Calculate the total count of divisors for the number 360360 using the prime factorization method.

Solution:

  1. Perform prime factorization of 360360: 360=2×180=22×90=23×45=23×32×51\begin{array}{r} 360 = 2 \times 180 \\ = 2^2 \times 90 \\ = 2^3 \times 45 \\ = 2^3 \times 3^2 \times 5^1 \end{array}
  2. Identify the exponents of the prime factors:
  • For prime factor 22, the exponent a1=3a_1 = 3.
  • For prime factor 33, the exponent a2=2a_2 = 2.
  • For prime factor 55, the exponent a3=1a_3 = 1.
  1. Apply the formula (a1+1)(a2+1)(a3+1)(a_1 + 1)(a_2 + 1)(a_3 + 1): Count=(3+1)×(2+1)×(1+1)\text{Count} = (3 + 1) \times (2 + 1) \times (1 + 1) Count=4×3×2=24\text{Count} = 4 \times 3 \times 2 = 24

Explanation:

The number 360360 has 2424 divisors in total. This formula accounts for all possible combinations of the prime factors.