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 a17. 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
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
Software engineering
Infrastructure & security
Computer science
Hardware & engineering