Learn on PengiThe Art of Problem Solving: Prealgebra (AMC 8)Chapter 3: Number Theory

Lesson 3: Prime Numbers

In this Grade 4 AMC Math lesson from The Art of Problem Solving: Prealgebra, students learn to define and identify prime and composite numbers, understanding that a prime has exactly two positive divisors while a composite has more than two. Students practice listing all primes less than 20 and apply efficient primality testing techniques, including the rule that only primes whose squares are less than or equal to the number being tested need to be checked. The lesson also introduces the Sieve of Eratosthenes as a method for generating lists of prime numbers.

Section 1

Prime and Composite Numbers

Property

A counting number (larger than 1) that is evenly divisible only by 1 and itself is called a prime number. A counting number larger than 1 that is not prime is called composite.

Examples

The number 17 is prime because its only factors are 1 and 17.
The number 25 is composite because it is divisible by 5, in addition to 1 and 25. Its factors are 1, 5, and 25.
The number 2 is the smallest prime number and the only even prime. All other even numbers are composite because they are divisible by 2.

Explanation

Think of prime numbers as basic building blocks; they only have two factors, 1 and themselves. Composite numbers are built from primes and can be divided by more than just 1 and themselves. The number 1 is neither prime nor composite.

Section 2

Square Root Optimization for Prime Testing

Property

To test if a number $n$ is prime, only check divisibility by primes $p$ where $p \leq \sqrt{n}$ . If no prime up to $\sqrt{n}$ divides $n$ , then $n$ is prime.

Examples

Section 3

Sieve of Eratosthenes Algorithm

Property

The Sieve of Eratosthenes is an algorithm to find all prime numbers up to a given limit $n$ : Start with all numbers from $2$ to $n$ , then systematically eliminate multiples of each prime, beginning with $2$ .

Examples

Lesson overview

Expand to review the lesson summary and core properties.

Expand

Section 1

Prime and Composite Numbers

Property

A counting number (larger than 1) that is evenly divisible only by 1 and itself is called a prime number. A counting number larger than 1 that is not prime is called composite.

Examples

The number 17 is prime because its only factors are 1 and 17.
The number 25 is composite because it is divisible by 5, in addition to 1 and 25. Its factors are 1, 5, and 25.
The number 2 is the smallest prime number and the only even prime. All other even numbers are composite because they are divisible by 2.

Explanation

Section 2

Square Root Optimization for Prime Testing

Property

To test if a number $n$ is prime, only check divisibility by primes $p$ where $p \leq \sqrt{n}$ . If no prime up to $\sqrt{n}$ divides $n$ , then $n$ is prime.

Examples

Section 3

Sieve of Eratosthenes Algorithm

Property

Examples

Overview

Lesson overview

Review the lesson summary and core properties without leaving the current page.

Overview

Section 1

Prime and Composite Numbers

Property

A counting number (larger than 1) that is evenly divisible only by 1 and itself is called a prime number. A counting number larger than 1 that is not prime is called composite.

Examples

The number 17 is prime because its only factors are 1 and 17.
The number 25 is composite because it is divisible by 5, in addition to 1 and 25. Its factors are 1, 5, and 25.
The number 2 is the smallest prime number and the only even prime. All other even numbers are composite because they are divisible by 2.

Explanation

Section 2

Square Root Optimization for Prime Testing

Property

To test if a number $n$ is prime, only check divisibility by primes $p$ where $p \leq \sqrt{n}$ . If no prime up to $\sqrt{n}$ divides $n$ , then $n$ is prime.