A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and so on. Numbers like 4, 6, and 9 are not prime because they have more than two divisors. For example, 4 equals 2 times 2 and has divisors 1, 2, and 4. The number 1 is not considered prime because it has only one divisor, and 2 is special as the only even prime number.
Composite numbers are natural numbers greater than 1 that are not prime, meaning they have more than two positive divisors. Looking at numbers 1 through 20, we can classify each as prime, composite, or neither. Composite numbers can be broken down into prime factors. For example, 12 equals 2 squared times 3, 15 equals 3 times 5, and 18 equals 2 times 3 squared. We can visualize this factorization using factor trees, which systematically break down composite numbers into their prime components.
The trial division method is the fundamental approach to test if a number is prime. To test if n is prime, we divide n by all numbers from 2 up to the square root of n. If any division is exact, n is composite; otherwise, n is prime. We only need to test up to the square root because if n equals a times b and a is greater than the square root of n, then b must be less than the square root, so we would have already found b as a divisor. Let's test if 29 is prime: the square root of 29 is about 5.4, so we test 2, 3, and 5. None divide evenly, so 29 is prime. For 91, we find that 91 divided by 7 equals 13 exactly, so 91 is composite.
The Sieve of Eratosthenes is an ancient Greek algorithm for efficiently finding all prime numbers up to a given limit. We start by listing all numbers from 2 to n. Beginning with 2, we keep it as prime and cross out all its multiples. Then we move to the next unmarked number, which is 3, keep it as prime, and cross out its multiples. We continue this process with 5, 7, and so on until we reach the square root of n. The numbers that remain unmarked are all the prime numbers up to n. This method is very efficient for finding multiple primes at once.
Prime numbers have several fascinating properties. First, Euclid proved there are infinitely many primes using a clever contradiction argument. The Prime Number Theorem shows that primes become less dense as numbers get larger - approximately n divided by the natural log of n primes exist below n. Twin primes are pairs that differ by 2, like 3 and 5, or 11 and 13. The Fundamental Theorem of Arithmetic states that every integer greater than 1 has a unique prime factorization. For example, 60 equals 2 squared times 3 times 5, and this factorization is unique. These properties make primes the building blocks of all integers.