A prime number is a whole number greater than \(1\) that has exactly two positive divisors:
\(1\) and itself. For example, \(2\), \(3\), \(5\), \(7\), and \(11\) are prime.
A composite number is a whole number greater than \(1\) that has more than two positive divisors.
1. Definition of a prime number
A number \(p\) is prime if
\[
\begin{aligned}
p &> 1
\end{aligned}
\]
and the only positive divisors of \(p\) are
\[
\begin{aligned}
1 \quad \text{and} \quad p.
\end{aligned}
\]
The number \(1\) is not prime, because it has only one positive divisor.
It is also not composite.
2. Primes in an interval
If the user enters a start value \(a\) and an end value \(b\), the calculator searches the inclusive interval
\[
\begin{aligned}
[a,b].
\end{aligned}
\]
This means it includes both endpoints. The calculator returns every prime \(p\) satisfying
\[
\begin{aligned}
a \le p \le b.
\end{aligned}
\]
3. Trial division idea
A direct way to test whether \(n\) is prime is to check whether any integer from \(2\) up to \(\sqrt n\) divides \(n\).
If none of them divides \(n\), then \(n\) is prime.
\[
\begin{aligned}
\text{test divisors only up to } \sqrt n.
\end{aligned}
\]
We only need to test up to \(\sqrt n\) because if
\[
\begin{aligned}
n = ab,
\end{aligned}
\]
then at least one of \(a\) or \(b\) must be less than or equal to \(\sqrt n\).
4. Sieve of Eratosthenes
The Sieve of Eratosthenes is faster when we need many primes in a range.
Instead of testing every number separately, it marks composite numbers in bulk.
The method is:
- Write all integers from \(2\) to \(b\).
- Start with \(2\), the first prime.
- Mark all multiples of \(2\) greater than \(2\) as composite.
- Move to the next unmarked number, which is prime.
- Mark its multiples as composite.
- Repeat until the base prime is greater than \(\sqrt b\).
- The unmarked numbers are prime.
5. Why marking starts at \(p^2\)
When the sieve reaches a prime \(p\), it starts marking from \(p^2\), not from \(2p\).
Smaller multiples of \(p\) have already been marked by smaller primes.
For example, when \(p=5\), the smaller multiples
\[
\begin{aligned}
10,\ 15,\ 20
\end{aligned}
\]
have already been marked by \(2\) or \(3\). Therefore, the first new multiple to mark is
\[
\begin{aligned}
5^2=25.
\end{aligned}
\]
6. Prime-counting function
The prime-counting function \(\pi(x)\) gives the number of primes less than or equal to \(x\).
\[
\begin{aligned}
\pi(x) &= \#\{p\le x : p \text{ is prime}\}.
\end{aligned}
\]
The number of primes in the inclusive interval \([a,b]\) is
\[
\begin{aligned}
\pi(b)-\pi(a-1).
\end{aligned}
\]
7. Worked example: primes from 1 to 100
We want all primes in
\[
\begin{aligned}
[1,100].
\end{aligned}
\]
Since \(1\) is not prime, the prime search effectively starts at \(2\).
The sieve needs base primes up to
\[
\begin{aligned}
\sqrt{100}=10.
\end{aligned}
\]
The base primes up to \(10\) are
\[
\begin{aligned}
2,\ 3,\ 5,\ 7.
\end{aligned}
\]
Mark multiples of each of these primes. The unmarked numbers from \(2\) to \(100\) are:
\[
\begin{aligned}
2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\\
43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71,\ 73,\ 79,\ 83,\ 89,\ 97.
\end{aligned}
\]
Therefore, there are
\[
\begin{aligned}
25
\end{aligned}
\]
primes from \(1\) to \(100\).
8. Prime density
Prime density in a finite interval means the fraction of numbers in the interval that are prime:
\[
\begin{aligned}
\text{density}
&= \frac{\#\text{ primes in }[a,b]}{b-a+1}.
\end{aligned}
\]
For the interval \([1,100]\),
\[
\begin{aligned}
\text{density}
&= \frac{25}{100}\\
&= 0.25\\
&= 25\%.
\end{aligned}
\]
9. Prime gaps
A prime gap is the difference between consecutive primes.
For example, between \(23\) and \(29\), the gap is
\[
\begin{aligned}
29-23=6.
\end{aligned}
\]
In a selected range, an average prime gap can be estimated using the first and last prime:
\[
\begin{aligned}
\text{average gap}
&= \frac{p_{\text{last}}-p_{\text{first}}}{N-1},
\end{aligned}
\]
where \(N\) is the number of primes in the range.
10. Why primes become less dense
Primes become less frequent on average as numbers grow larger.
A rough advanced estimate is that the density of primes near \(n\) behaves like
\[
\begin{aligned}
\frac{1}{\ln n}.
\end{aligned}
\]
This comes from the Prime Number Theorem, which states approximately that
\[
\begin{aligned}
\pi(x)\sim \frac{x}{\ln x}.
\end{aligned}
\]
This is only an approximation for large \(x\), not an exact counting rule.
11. Formula summary
| Concept |
Formula or rule |
Meaning |
| Prime number |
\(p>1\), divisors only \(1\) and \(p\) |
A number with exactly two positive divisors |
| Composite number |
\(n=ab\), with \(1<a<n\) |
A number greater than \(1\) that is not prime |
| Sieve limit |
\(\lfloor\sqrt b\rfloor\) |
Largest base factor needed to mark composites up to \(b\) |
| Interval count |
\(\pi(b)-\pi(a-1)\) |
Number of primes in \([a,b]\) |
| Prime density |
\(\frac{\#\text{ primes}}{b-a+1}\) |
Fraction of interval values that are prime |
| Average prime gap |
\(\frac{p_{\text{last}}-p_{\text{first}}}{N-1}\) |
Average spacing between listed primes |
12. Common mistakes
- Counting \(1\) as a prime number.
- Forgetting that \(2\) is prime and is the only even prime.
- Checking divisibility beyond \(\sqrt n\) when testing one number.
- Forgetting that the interval \([a,b]\) includes both \(a\) and \(b\).
- Marking a prime itself as composite in the sieve.
- Starting the sieve marking from \(2p\) instead of \(p^2\), which is correct but less efficient.
Key idea: the sieve removes composites by marking multiples, leaving exactly the primes.
