Prime Numbers and Fibonacci Numbers Explained
What primes are, how trial division and the sieve of Eratosthenes find them, how Fibonacci numbers approach the golden ratio, and which ones are prime.
A prime is a whole number greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11 and so on, with 25 of them below 100. To test a number n you only need to try divisors up to the square root of n, so 97 needs checking against 2 through 9 and is prime. Fibonacci numbers are a different family: each term is the sum of the two before it (1, 1, 2, 3, 5, 8, 13, …), and the ratio of neighbours settles toward the golden ratio, about 1.6180339887. The two families meet in a short list of numbers that are both Fibonacci and prime.
What counts as prime
Every whole number above 1 is either prime or a product of primes, and that product is unique apart from order (the fundamental theorem of arithmetic). So 91 = 7 × 13 and 221 = 13 × 17 are composite, while 2 is the only even prime. The numbers 0 and 1 are neither. Splitting a number into its primes is called prime factorization.
Trial division up to the square root
If n = a × b with a ≤ b, then a ≤ √n, so a composite number always has a divisor no larger than its square root. You can stop testing there.
| n | Square root (whole part) | Result |
|---|---|---|
| 97 | 9 | prime, no divisor from 2 to 9 |
| 91 | 9 | composite, 91 = 7 × 13 |
| 221 | 14 | composite, 221 = 13 × 17 |
| 7,919 | 88 | prime |
| 10,001 | 100 | composite, 10,001 = 73 × 137 |
| 65,537 | 256 | prime, 255 trial divisors (2 to 256) |
Testing only primes as divisors saves more work: if no prime up to √n divides n, then n is prime. Trial division is fast for numbers you can type by hand and slows down for numbers with dozens of digits. A prime number checker does the test for you.
The sieve of Eratosthenes
To list every prime up to a limit, write the numbers out and strike off multiples instead of testing each number. For a limit of 100, take the primes up to its square root (2, 3, 5 and 7), and for each one strike every multiple from its square onward: 4, 6, 8, … for 2; 9, 12, 15, … for 3; 25, 30, 35, … for 5; 49, 56, 63, … for 7. After that, 1 and 74 composites are gone and 25 primes remain.
| Range | Primes | Count |
|---|---|---|
| 1 to 10 | 2, 3, 5, 7 | 4 |
| 11 to 20 | 11, 13, 17, 19 | 4 |
| 21 to 30 | 23, 29 | 2 |
| 31 to 40 | 31, 37 | 2 |
| 41 to 50 | 41, 43, 47 | 3 |
| 51 to 60 | 53, 59 | 2 |
| 61 to 70 | 61, 67 | 2 |
| 71 to 80 | 71, 73, 79 | 3 |
| 81 to 90 | 83, 89 | 2 |
| 91 to 100 | 97 | 1 |
Primes thin out as numbers grow, but slowly.
| Up to | Primes | Share of numbers | n ÷ ln n |
|---|---|---|---|
| 10 | 4 | 40.000% | 4.3 |
| 100 | 25 | 25.000% | 21.7 |
| 1,000 | 168 | 16.800% | 144.8 |
| 10,000 | 1,229 | 12.290% | 1,085.7 |
| 100,000 | 9,592 | 9.592% | 8,685.9 |
The last column, n divided by the natural logarithm of n, is the rough estimate given by the prime number theorem. It runs a little low at these sizes but tracks the trend.
The Fibonacci sequence
Start with 1 and 1, or with 0 and 1 if you count from F₀. Each term after that is the sum of the previous two: F(n) = F(n−1) + F(n−2). The first terms from F₀ are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. F₃₀ is 832,040 and F₅₀ is 12,586,269,025. The Fibonacci calculator generates any term you need.
Binet’s formula and the golden ratio
A closed form gives any term directly. With φ = (1 + √5) ÷ 2 ≈ 1.6180339887 and ψ = (1 − √5) ÷ 2:
F(n) = (φⁿ − ψⁿ) ÷ √5
Since |ψ| is below 1, ψⁿ vanishes quickly, so F(n) is just φⁿ ÷ √5 rounded to the nearest whole number. For n = 10, φ¹⁰ ÷ √5 = 55.0036, which rounds to 55. For n = 20 it is 6,765.00003, which rounds to 6,765.
The same formula explains the ratio of neighbours.
| n | F(n) | F(n+1) | F(n+1) ÷ F(n) | Distance from φ |
|---|---|---|---|---|
| 2 | 1 | 2 | 2.00000000 | 3.82 × 10⁻¹ |
| 3 | 2 | 3 | 1.50000000 | 1.18 × 10⁻¹ |
| 4 | 3 | 5 | 1.66666667 | 4.86 × 10⁻² |
| 6 | 8 | 13 | 1.62500000 | 6.97 × 10⁻³ |
| 10 | 55 | 89 | 1.61818182 | 1.48 × 10⁻⁴ |
| 20 | 6,765 | 10,946 | 1.61803400 | 9.77 × 10⁻⁹ |
| 30 | 832,040 | 1,346,269 | 1.61803399 | 6.46 × 10⁻¹³ |
The ratios swing above and below φ and close in on it.
Fibonacci numbers that are prime
Among the first 100 terms, these are the Fibonacci numbers greater than 1 that are prime:
| Index n | F(n) |
|---|---|
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 7 | 13 |
| 11 | 89 |
| 13 | 233 |
| 17 | 1,597 |
| 23 | 28,657 |
| 29 | 514,229 |
| 43 | 433,494,437 |
| 47 | 2,971,215,073 |
| 83 | 99,194,853,094,755,497 |
Beyond index 4, every prime Fibonacci number in the list has a prime index (5, 7, 11, 13, …). A prime index is not enough, though: 19 is prime, but F(19) = 4,181 = 37 × 113. For the larger entries, use the prime factorization calculator to confirm what a given term splits into.
Why big primes matter
Public-key cryptography, such as RSA, relies on the fact that multiplying two large primes is easy while recovering them from the product is believed to be very hard.
Quick reference
- A prime has exactly two divisors; 2 is the only even one.
- To test n, divide by every candidate up to √n.
- To list the primes up to a limit, sieve them.
- Fibonacci terms add the previous two; φⁿ ÷ √5, rounded, gives the nth.
- Neighbouring ratios approach 1.6180339887.
All lists and values here were produced by a short Python program using integer arithmetic for the sieve and trial division, and 50-digit decimals for the closed form.
Updated 2026-11-04