Micro-questions over the number theory module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. Why it exists

1. Give the alarm clock illustration.

Answer

Alarm A rings every 12 minutes, B every 18. They first coincide at LCM(12, 18) = 36 minutes.

2. What asymmetry does RSA rest on?

Answer

Multiplying two 500-digit primes is instant; factoring the 1000-digit result takes thousands of years of supercomputer brute force.


B. The vocabulary

3. What is a prime number?

Answer

An integer with no positive divisors other than 1 and itself.

4. What is a composite number?

Answer

An integer with more than two divisors.

5. Are 0 and 1 prime?

Answer

Neither prime nor composite. Always handle explicitly as False.

6. Define GCD and LCM.

Answer

GCD: the largest number dividing both and — GCD(24, 36) = 12. LCM: the smallest number that is a multiple of both — LCM(12, 18) = 36.


C. Primality testing

7. State the symmetric factor rule.

Answer

Every factor pair satisfies . If both exceeded their product would exceed — so at least one factor of every pair must be .

8. What follows for the algorithm?

Answer

You only need to test divisors up to — .

9. Quantify the saving at .

Answer

A billion operations versus 31,622 — about a 30,000× speedup.

10. Why write while i * i <= n rather than i <= sqrt(n)?

Answer

It avoids floating-point entirely — no rounding error at the boundary, and integer multiplication is exact.


D. The sieve

11. What does testing each number individually cost, and what does the sieve cost?

Answer

Individually: . Sieve: — near-linear.

12. Describe the mechanism.

Answer

Mark everything prime, then for each surviving , cross out its multiples.

13. Where should the crossing-out start, and why?

Answer

At . Multiples of smaller than — , — have already been crossed out by smaller primes.

14. What is its space cost?

Answer

— a boolean per number, which is the sieve’s real constraint at large .


E. Euclid

15. State the Euclidean identity.

Answer

16. Write the loop.

Answer
while b:
    a, b = b, a % b
return a

17. What is its complexity?

Answer

.

18. How do you get LCM from GCD?

Answer

19. What is the overflow trap in that formula, and the fix?

Answer

In C++ or Java, a * b can overflow a 32-bit integer before the division. Fix: divide first — (a // gcd(a,b)) * b.


F. Costs

20. Give the four complexities.

Answer

Primality check , space. Divisor counting , . Sieve , . Euclidean GCD , .

21. When do you use the sieve rather than repeated primality checks?

Answer

When you need all primes up to , or many primality queries in the same range. For one number, with space wins.

22. Summarise the module in one sentence.

Answer

Factors pair up around , multiples of a prime can be crossed out from its square, and GCD falls out of repeated modulo — three small facts that make the rest cheap.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Algorithms