How many values of j does divisors(63) check, as written in the book?
Show answer and solution
Answer: 63
- The algorithm checks every j from 1 to 63.
- 63 checks, whatever the number of divisors. Divisor pairs can cut this to about √63.
CBSE Class 9 · NCERT Ganita Manjari, Part II · Chapter 11
Step-by-step procedures: column addition, divisor lists, gcd by scanning, and Euclid's and Āryabhaṭa's fast methods. This chapter is broken into 14 skills; each has an animated lesson and practice questions that never repeat.
Al-Khwārizmī wrote on Indian numerals around 820 CE; Euclid wrote down the subtraction gcd; Āryabhaṭa (499 CE) used division.
Precise steps built from basic steps we can already do, with repeated steps, conditions, named values and a stopping rule.
Align from the right, add each column with the carry, carry 1 when a column reaches 10, and write the last carry.
Counting takes as many steps as the sum; columns take one step per digit. One more digit: 10 times the dots, one more column.
Start with an empty list; for each j from 1 to n, add j if it divides n. divisors(18) = [1, 2, 3, 6, 9, 18].
Every divisor j ≤ √n has a partner n ÷ j, so checking 1 to √n is enough. 18: (1, 18), (2, 9), (3, 6).
Keep each divisor of m that is also in divisors(n); the lists are increasing, so the gcd is the rightmost common divisor.
One scan to max(m, n), then only to min(m, n), then no list at all: keep the most-recent-common-divisor.
Scanning to min(m, n) grows 10 times per extra digit; good algorithms grow with the number of digits instead.
gcd(m, n) = gcd(n, m − n), and gcd(m, 0) = m. Swap if m < n, subtract, repeat. gcd(375, 825) takes 7 reductions.
Replace m − n by m mod n, the remainder: gcd(99, 2) takes 2 reductions instead of 51. Long division layout.
n is prime when divisors(n) has exactly two entries; filter divisors(n) for the primes; 180 = 2² × 3² × 5¹.
Scan multiples of the larger number until one is a multiple of the smaller, or use gcd × lcm = m × n.
gcd(51000, 81000), gcd(2587392, 157656), counting reductions, divisor lists and carries from the exercises.
An algorithm is a systematic, step-by-step procedure to solve a problem. Each step is written precisely and uses only basic steps we already know how to do, such as adding two single digits or checking whether one number divides another.
Steps can repeat (for each j from 1 to n …), can be conditional (… if j divides n, add j), use named values (j, list-of-divisors), and must stop. When we give an algorithm we also justify that it is correct, and we can count how many steps it takes.
1. Start with an empty list-of-divisors. 2. For each number j in 1, 2, 3, …, n: if j divides n, add j to list-of-divisors.
Remember: Algorithm = precise basic steps, repeated and conditional, with names, a stop, and a reason it works.
In the portal every question is generated fresh, so you never see the same one twice, and a wrong answer tells you which mistake you made.
How many values of j does divisors(63) check, as written in the book?
Answer: 63
Running the most-recent-common-divisor scan for gcd(81, 63), what is its value just after k = 6 is checked?
Answer: 3
divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375] and divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]. What is gcd(375, 825)?
Answer: 75
Check every j from 1 to n, including 1 and n itself, or find the partner n ÷ j of each small divisor.
The algorithm stops at gcd(m, 0), and the answer is m, the non-zero number.
An algorithm is a precise list of basic steps: some repeat, some happen only when a condition holds, and it must stop.
One more digit makes a number about 10 times bigger: scanning work grows 10 times, column work by one step.
A common divisor must divide both numbers: check it against both lists.
A recipe is an algorithm: precise steps, some repeated ('stir every minute'), some conditional ('if it is too thick, add water'), and a clear point where you stop.
The shopkeeper adding ₹473 and ₹695 on paper runs the column algorithm: right to left, digit plus carry. Nobody counts 1168 coins one by one.
The largest square tile that fits a 375 cm by 825 cm floor exactly, or the biggest equal boxes for 84 laddoos and 126 barfis, is a gcd: 75 cm and 42 per box.
One bus every 12 minutes, another every 18: they leave together again after lcm(12, 18) = 36 minutes. Festivals, shift rotas and traffic lights work the same way.
Log in with your phone number: lessons for all 14 skills, endless practice, a chapter test and a report that shows exactly what to fix.