Question Bank
Prime and Sieve Quiz
Difficulty: Medium
Code-first drills on primality testing, the Sieve of Eratosthenes, and smallest-prime-factor tables. Includes complexity reasoning and one prime-factorization walk.
Prime and Sieve Quiz
Code-first drills on primality testing, the Sieve of Eratosthenes, and smallest-prime-factor tables. Includes complexity reasoning and one prime-factorization walk.
729 views
8
Implement a trial-division primality test that runs in O(sqrt(n)). Explain the i * i <= n loop bound.
Examples
Example 1:
Input: n = 97
Output: true
Explanation: If n = a * b with a <= b, then a <= sqrt(n). So the smallest non-trivial divisor (if any) lies at or below sqrt(n). Loop while i * i <= n. 97 has no divisor up to 9, so it is prime.Example 2:
Input: n = 100
Output: false
Explanation: 100 = 2 * 50, caught immediately by the parity check. The function returns false without entering the odd-divisor loop.Implement the Sieve of Eratosthenes that returns an array of all primes <= n. Justify the well-known O(n log log n) total work.
Examples
Example 1:
Input: n = 30
Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Explanation: Mark composites starting at p * p. Once p is confirmed prime, every smaller multiple was already marked by some prime <= p - 1. Total work sum_p (n / p) = O(n log log n) by Mertens.Factor 360 into its prime factorization using trial division. Show the work as a multiset of primes and explain the time bound.
Build a smallestPrimeFactor(n) table via a linear sieve in O(n). Use it to factor 84 in O(log 84) lookups.