Primes and Composites: Practice

Use the digit-sum rule for $3$ and the last-digit rule for $5$ to screen them.

$51 = 3 \times 17, \quad 57 = 3 \times 19, \quad 55 = 5 \times 11$

Those three are composite. For $53$: it is odd, digit sum $5 + 3 = 8$ is not a multiple of $3$, it does not end in $0$ or $5$, and $7 \times 7 = 49 < 53$ while $8 \times 8 = 64 > 53$, so only $7$ is left to try, and $53 \div 7$ leaves a remainder. So $53$ is prime.

Three of these are prime; one hides a factor. Try squaring small divisors.

$49 = 7 \times 7$

So $49$ is composite. The numbers $41$, $43$, and $47$ have no factor besides $1$ and themselves, so they are prime.

Screen with the quick rules: digit sums for $3$ and last digit for $5$.

$63 = 9 \times 7, \quad 69 = 3 \times 23, \quad 65 = 5 \times 13$

Those are composite. For $67$: odd, digit sum $13$ (not a multiple of $3$), not ending in $0$ or $5$, and $7 \times 7 = 49 < 67 < 81 = 9 \times 9$, so only $7$ remains, and $67 \div 7$ has a remainder. So $67$ is prime.

Three of these are prime. Test the fourth past the obvious small divisors.

$91 = 7 \times 13$

So $91$ is composite, with the hidden factor $7$. The numbers $89$, $83$, and $79$ are all prime.

Test divisors in increasing order, starting at $2$.

$50 \text{ ends in } 0 \;\Rightarrow\; \text{even}, \text{ so } 50 = 2 \times 25$

The very first divisor, $2$, already divides $50$, so $50$ is composite. There is no need to try $3$, $5$, or $7$.

Check $2$ through $9$, keeping only numbers with exactly two factors.

$2, \; 3, \; 5, \; 7 \to \text{prime}$

That is four primes. The numbers $4, 6, 8, 9$ are composite, and $1$ is excluded.

A last digit of $4$ is even, so $2$ divides the number.

$n > 2 \text{ and even} \;\Rightarrow\; 1, 2, n \text{ are factors}$

That third factor $2$ makes it composite. Any number greater than $2$ ending in $0, 2, 4, 6,$ or $8$ is composite at a glance.

Three of these are prime (just two factors each), so compare against $12$.

$12 = 1 \times 12 = 2 \times 6 = 3 \times 4 \;\Rightarrow\; \text{factors } 1, 2, 3, 4, 6, 12$

That is six factors. Each of $7$, $11$, and $13$ has only two, so $12$ has the most.

Apply the stopping rule: test divisors only while $d \times d \le n$.

$11 \times 11 = 121 > 73$

Since $11$ squared already passes $73$, you stop. No smaller divisor worked, so $73$ is prime; trying $11$ is unnecessary.

Use the digit-sum rule for $3$ to find the one with an extra factor.

$3 + 9 = 12 = 3 \times 4, \text{ so } 39 = 3 \times 13$

Thus $39$ is composite. The numbers $31$, $37$, and $41$ are all prime.

Test both numbers in each pair.

$23 \text{ and } 29: \text{ each odd, not a multiple of } 3 \text{ or } 5, \text{ and } 7 \times 7 = 49 > 29$

So both $23$ and $29$ are prime. Every other pair contains a multiple of $3$ or $5$, so those numbers are composite.

Drop the obvious composites: $45$ ends in $5$, $46$ is even, and $49 = 7 \times 7$.

$43: \text{ odd, digit sum } 7, \text{ not ending in } 0 \text{ or } 5, \quad 7 \times 7 = 49 > 43$

So only $2, 3, 5$ need checking, and none divides $43$. So $43$ is prime.