Question bank — Prime numbers — Sieve of Eratosthenes, primality testing

True — if a prime $p>2$ were even it would be divisible by $2$, giving a third divisor ($1,2,p$), so it could not be prime. Thus $2$ is the only even prime. ::: True; $2$ is the lone even prime, every other even number has $2$ as a proper divisor.

True — $p\cdot q$ has the divisor $p$ with $1<p<pq$, which is exactly the definition of composite. Such a number (a product of exactly two primes) is called a semiprime, e.g. $91=7\times 13$; see Factorisation. ::: True; the factors $p$ and $q$ are proper divisors, so the product (a semiprime) is composite by definition.

$2$, $3$, or $5$, it must be prime. False — you must trial-divide up to $\lfloor \sqrt{n}\rfloor$ (floor = round down, defined above). $49=7^2$ and $77=7\times 11$ dodge $2,3,5$ yet are composite (see Divisibility rules for why small tests aren't enough). ::: False; $49=7\times 7$ and $77=7\times 11$ pass the $2,3,5$ tests but are composite.

False — Euclid's argument: multiply all known primes, add $1$; the result is divisible by no listed prime, so a new prime must exist. Primes are infinite. ::: False; primes are infinite (Euclid: $p_1{p}_2\cdots p_k+1$ forces a prime outside any finite list).

False — a prime's only divisors are $1$ and itself, so two distinct primes have $\gcd =1$; they are coprime (see GCD and LCM). ::: False; distinct primes are coprime, their only shared divisor is $1$.

True — this is guaranteed by the Fundamental Theorem of Arithmetic: every integer $>1$ breaks into a product of primes, so the smallest divisor above $1$ must itself be prime. ::: True; the Fundamental Theorem of Arithmetic guarantees a prime factorisation, hence a prime factor.

$\gcd (p,q)=1$ for distinct primes implies $\mathrm{lcm}(p,q)=pq$. True — since $\gcd \times \mathrm{lcm}=pq$ and $\gcd =1$, the LCM absorbs the full product. This is the GCD and LCM identity applied to coprime primes. ::: True; $\gcd \cdot \mathrm{lcm}=pq$ and $\gcd =1$ force $\mathrm{lcm}=pq$.

Logical mistake. The definition demands exactly two distinct divisors. For $1$, "$1$" and "itself" coincide — only one divisor exists. Admitting $1$ would also wreck unique factorisation ($6=2\cdot 3=1\cdot 2\cdot 3=\dots$). ::: Logical mistake: $1$ has only one distinct divisor, not two, and allowing it breaks uniqueness in the Fundamental Theorem of Arithmetic.

$n$ is prime, stop dividing once you pass a few small numbers with no hit." — logical mistake? Logical mistake. You must reach $\lfloor \sqrt{n}\rfloor$. If $n=ab$ with $a\le b$, then $a\le \sqrt{n}$, so a missed divisor can hide right up to the square root — e.g. $221=13\times 17$ needs testing up to $\lfloor \sqrt{221}\rfloor =14$. ::: Logical mistake: the smaller factor can be as large as $\sqrt{n}$; stopping early misses divisors like $13$ in $221=13\times 17$.

$p$ from $2p$." — logical mistake or tuning tip? Tuning tip, not a mistake. The result is correct, merely wasteful: every multiple $k\cdot p$ with $k<p$ was already crossed while sieving the smaller prime $k$. The first new multiple is $p^2$. ::: Tuning tip (not wrong, just slow): multiples below $p^2$ are already crossed by smaller primes, so starting at $p^2$ saves work.

$N$ to be safe." — logical mistake or tuning tip? Tuning tip, not a mistake. It still finds the right primes, just does needless work: any composite $\le N$ has a prime factor $\le \sqrt{N}$, so once $p>\sqrt{N}$ nothing new can be crossed (see Time complexity Big-O). ::: Tuning tip (correct but slow): stop at $p\le \sqrt{N}$; every surviving number above that is automatically prime.

$\sqrt{n}$ trial division and the sieve's $p^2$ start are two separate tricks." — logical mistake? Logical mistake (a misconception). They are the same fact wearing two hats: the smaller factor of any pair sits below $\sqrt{n}$. Trial division reads it as "test to $\sqrt{n}$"; the sieve reads it as "start at $p^2$ and stop at $\sqrt{N}$." ::: Logical mistake: both come from one fact — the small factor of a pair is $\le \sqrt{n}$.

$0$ and negative numbers can be prime if they have few factors." — logical mistake? Logical mistake. Primality is defined only for natural numbers $p>1$. $0$ is divisible by everything, and negatives fall outside the definition entirely. ::: Logical mistake: the definition requires $p>1$; $0$, $1$, and negatives are excluded by convention.

$1$ from the primes make factorisation unique? If $1$ counted as prime, you could pad any factorisation with extra $1$s ($12=2^2\cdot 3=1\cdot 2^2\cdot 3=\dots$), so "the" prime factorisation would no longer be single. Excluding $1$ pins it down. ::: Because $1$ could be multiplied in endlessly, destroying the uniqueness the Fundamental Theorem of Arithmetic promises.

$2$ special among the primes? It is the only even prime; every larger even number carries $2$ as a proper divisor. Its evenness makes it the one prime that breaks the "all primes are odd" pattern. ::: Because it is the sole even prime — all other evens are composite (divisible by $2$).

Modular arithmetic? When the modulus is prime, every nonzero remainder has a multiplicative inverse, so division "works" — a property composite moduli lack. Primes give the cleanest arithmetic systems. ::: Because a prime modulus makes every nonzero element invertible, unlike composite moduli.

Composites are the numbers that fold into a rectangle (see the first figure) — easy to generate as multiples. Removing all of them leaves exactly the numbers that are not rectangles, i.e. the primes, without testing each one. ::: Because multiples (the "rectangle" numbers) are easy to list and cross out; whatever survives must be prime.

$O(\sqrt{n})$ and not $O(n)$? We only test divisors up to $\sqrt{n}$, and any divisor above it has a partner below it. So the number of checks scales with $\sqrt{n}$ — see Time complexity Big-O. ::: Because only divisors up to $\sqrt{n}$ need testing, giving $\sqrt{n}$ checks instead of $n$.

$2$ handled correctly by "test only odd divisors" primality code? $2$ itself must be special-cased as prime before skipping evens; otherwise the shortcut that assumes odd inputs would misclassify it. ::: $2$ must be declared prime up front; the odd-only skip assumes the input is already known not to be $2$.

$N=0$? Nothing — the candidate list $2\dots N$ is empty (there is no integer between $2$ and $0$), so it correctly returns no primes, matching the fact that no primes exist $\le 0$. ::: The list is empty, correctly yielding no primes since none exist $\le 0$.

$N=1$? Nothing survives — the list $2\dots N$ is empty, so there are no primes $\le 1$, which is correct since $1$ is not prime. ::: The candidate list is empty, correctly yielding no primes (since $1$ is not prime).

$N=2$, does the sieve ever cross anything out? No — $p=2$ but $p^2=4>2=N$, so the loop stops immediately and $2$ survives as the only prime. This is the smallest working case. ::: No crossing occurs ($p^2=4>N$); $2$ survives, correctly the only prime $\le 2$.

$N=3$, what does the sieve do, and how does it extend the $N=2$ case? Again nothing gets crossed — $p=2$ has $p^2=4>3=N$, so the loop halts on the very first prime. Both $2$ and $3$ survive, which is right since $\{2,3\}$ are the primes $\le 3$. It shows the pattern from $N=2$ holds: while $p^2>N$, every candidate is auto-prime. ::: Nothing is crossed ($2^2=4>3$); both $2$ and $3$ survive, matching the primes $\le 3$ and extending the $N=2$ pattern.

$49$ a boundary case for trial division? Yes — its factor pair is $7\times 7$, so both factors equal $\sqrt{49}=7$. You must test up to and including $\lfloor \sqrt{n}\rfloor$, or you'd miss the equal-factor case. ::: Yes; $49=7\times 7$ means the divisor sits exactly at $\sqrt{n}$, so the loop must include $\lfloor \sqrt{n}\rfloor$.

$\sqrt{n}$? No — if both factors exceeded $\sqrt{n}$, their product would exceed $n$, a contradiction. That impossibility is the whole engine behind the $\sqrt{n}$ bound. ::: No; two factors both above $\sqrt{n}$ would multiply past $n$, which is impossible.

$n=p^2$ (a prime squared) prime, and how many divisors has it? Composite, with exactly three divisors: $1$, $p$, and $p^2$. It is the simplest composite that a naive "few small primes" check can miss when $p$ is not tiny. ::: Composite; it has three divisors ($1,p,p^2$), so it is never prime for any prime $p$.