Prime Numbers

This is a study of Prime Numbers and computers. This article is to just get started understanding Prime Numbers.

Definition of Prime Numbers

If I want to define a Prime Number, I could look to Wikipedia for a definition.

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.

Everything beyond that definition is just making it more complicated. This assumes that the use of the terms a natural number and a product are understood.

I am not here to teach all of basic math. That is why too many of these get complicated. But a natural number is a number that is an integer and is greater than zero. A product the the result of multiplying two numbers together.

Purpose

The purpose of this pursuit is to write a program to create a list of every prime number between one and one trillion, and to prove its acccuracy. Furthermore, it is to do this on a Raspberry Pi computer with its limited memory and storage capacity.

Available Equipment

I have limited equipment for performing this task. I am setting up two Raspberry Pi computers to dedicate to this pursuit and I want to prove that I can do this on both systems.

• Raspberry Pi 5 Model B Rev 1.0
• Raspberry Pi Zero 2 W Rev 1.0

As a matter of fact, both systems are busy with this task tfp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm lrcpc dcpop asimddphat I have created and they are both currently making their way. You might wonder about what progress these might have made?

Raspberry Pi 5 Model B Rev 1.0

Specifications:

Free Memory:

coelho@guarda:~/prime-number-gfortran-2 $ free
               total        used        free      shared  buff/cache   available
Mem:         4146320      829280      109872       69232     3545216     3317040
Swap:       16585216      425456    16159760

As of writing this document on August 23, 2026, at 8:27 in the morning, this system has listed every prime number between one and six hundered and forty-nine billion, and it is still working beyond that point.

The first results are posted on August 2, 2026 at 1:56 in the morning. This does not give you exact time running but it is fair to say that it has taken twenty-one days to get this far.

Raspberry Pi Zero 2 W Rev 1.0

Specifications:

Free Memory:

user@raspberrypizero2w:~ $ free
               total        used        free      shared  buff/cache   available
Mem:          425180      234256       22256        7944      237808      190924
Swap:        2125660       44356     2081304

As of writing this document on August 23, 2026, at 8:54 in the morning, this system has listed every prime number between one and fifty billion, and it is still working beyond that point.

The first results are posted on August 7, 2026 at 3:20 in the afternoon. This does not give you exact time running but it is fair to say that it has taken sixteen days to get this far.

Equipment Notes

Both of these systems are running 24 hours a day, 7 days a week, continuously. Each system has an attached one terrabyte hard disk drive for performing work on. This is less surprising on a Raspberry Pi 5, but more surprising on a Raspberry Pi Zero 2 W. The memory available is as listed. Note that the operating temperatures of each unit are both below tolerances, and thermal throttling has been eliminated. The progress of the Raspberry Pi 5 far outstrips the progress of the Raspberry Pi Zero 2 W, but this is to be expected.

How to Handle One Trillion

Generating primes up to a trillion isn’t just a test of CPU speed—it is a puzzle of memory management and storage limits. A naive approach would quickly exhaust the Rapberry Pi’s RAM or wear out the SD card. To pull this off on a Raspberry Pi Zero 2W with under 500 MB of RAM, the algorithm has to be as lean as the hardware.

The Standard Textbook Answer - The Sieve of Eratosthenes

A search for prime number methods often reveals The Sieve of Eratosthenes. Named after the ancient Greek mathematician who conceived it over two thousand years ago, it remains the most commonly cited algorithm for finding all prime numbers up to a given limit.

Wikipedia has an article. Let me quote the first two paragraphs.

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve’s key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.

A Python Program

Here I have a program written in Python to generate all of the prime numbers up to one million.

import sys
import time

def sieve_of_eratosthenes(limit):
    print(f"Generating all prime numbers up to {limit:,}...\n")

    start_time = time.time()

    # Create a boolean array initialized to True
    # Index = number, Value = is_prime
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime

    # Core Eratosthenes Logic
    for p in range(2, int(limit**0.5) + 1):
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False

    # Extract all numbers that remained True
    primes = [num for num, prime in enumerate(is_prime) if prime]

    elapsed_time = time.time() - start_time

    # Calculate Memory Footprint of the Main Sieve Array
    bytes_used = sys.getsizeof(is_prime)
    mb_used = bytes_used / (1024 * 1024)

    # Output Results
    print(f"Completed in: {elapsed_time:.4f} seconds")
    print(f"Total primes found: {len(primes):,}")
    print(f"First 10 primes: {primes[:10]}")
    print(f"Last 10 primes:  {primes[-10:]}")
    print(f"Memory allocated for sieve array: {mb_used:.2f} MB")

    return primes

### Run for 1,000,000
if __name__ == "__main__":
    primes = sieve_of_eratosthenes(1000000)

I can run this program on my Raspberry Pi Zero 2W.

username@raspberrypizero2w:~ $ python prime-million.py
Generating all prime numbers up to 1,000,000...

Completed in: 1.4674 seconds
Total primes found: 78,498
First 10 primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Last 10 primes:  [999863, 999883, 999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]
Memory allocated for sieve array: 7.63 MB

I have been working with prime numbers enough now to vouch for the total primes found, the first ten primes, and the last ten primes. Look at this. One and a half seconds on the least of the Raspberry Pi models.

I will now run this program on my Raspberry Pi 5 computer.

username@raspberrypi5 $ python3 prime-million.py
Generating all prime numbers up to 1,000,000...

Completed in: 0.1660 seconds
Total primes found: 78,498
First 10 primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Last 10 primes:  [999863, 999883, 999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]
Memory allocated for sieve array: 7.63 MB

And look at that! 0.1660 seconds! And this Raspberry Pi is currently under full CPU 100% load while calculating lists for myself.

So, go figure that I should be using this algorithm to calculate prime numbers up to one trillion, and I should be getting on a lot better with this kind of speed. You would think so. But there is another metric reported, memory usage. 7.63 MB is the reported usage, and on both Raspberry Pi units. That is not a lot of memory for this type of a computer, but this is where the culprit lies.

If you remember what I had posted earlier, I am running a program to acheive my goal on both a Raspberry Pi 5 and a Raspberry Pi Zero 2W. Although the Raspberry Pi 5 had a one week head start and more processing resources, both are well into the billions of prime numbers. What I am about to unfold about The Sieve of Eratosthenes took me aback.

To put it simply, a Raspberry Pi Zero 2W does not have the memory resources to produce these scales of prime numbers. However, neither does my Raspberry Pi 5, nor my does my Lenovo Debian Workstation with 8 GB RAM.

Another Python Program

This program will create the required arrays of bytes for calculations, and then comeback with the memory usage to store this information. This will then go through all of the possibilities from ten thousand, then one hundred thousand, one million, ten million, one hundred million, one billion, ten billion, one hundred billion, and finally one trillion. It will report when the memory allocation breaks the operating system.

import sys

def demonstrate_sieve_memory(limit):
    print(f"Testing limit N = {limit:,}")
    try:
        # Standard boolean array (1 byte per item reference in Python)
        sieve = [True] * (limit + 1)
        sieve[0] = sieve[1] = False

        bytes_used = sys.getsizeof(sieve)
        mb_used = bytes_used / (1024 * 1024)
        gb_used = mb_used / 1024

        print(f"  -> Allocation successful!")
        print(f"  -> RAM required: {mb_used:.2f} MB ({gb_used:.4f} GB)\n")

    except MemoryError:
        print(f"  -> FAILED: MemoryError (Out of Memory) at N = {limit:,}\n")

for power in range(4, 13):
    limit = 10**power
    demonstrate_sieve_memory(limit)

This is running the Python program on the Raspberry Pi Zero 2W. Note that the memory usage matches the memory usage reported when creating The Sieve of Eratosthenes for one million. But also note two items of distinction:

1. When prime numbers up to one hundred thousand are to be calculated, the memory requirements exceed the installed memory of the Raspberry Pi Zero 2W. While this means that it is possible, it is not recommended. Strain on the MicroSD card for the operating system is a bad thing.
2. The program would never create a list of prime numbers up to one billion on the Raspberry Pi Zero 2W. Yet I had reported that my Raspberry Pi Zero 2W server had created a list of prime numbers in excess of fifty billion and it is still going.

user@raspberrypizero2w:~ $ python3 prime-allocations.py
Testing limit N = 10,000
  -> Allocation successful!
  -> RAM required: 0.08 MB (0.0001 GB)

Testing limit N = 100,000
  -> Allocation successful!
  -> RAM required: 0.76 MB (0.0007 GB)

Testing limit N = 1,000,000
  -> Allocation successful!
  -> RAM required: 7.63 MB (0.0075 GB)

Testing limit N = 10,000,000
  -> Allocation successful!
  -> RAM required: 76.29 MB (0.0745 GB)

Testing limit N = 100,000,000
  -> Allocation successful!
  -> RAM required: 762.94 MB (0.7451 GB)

Testing limit N = 1,000,000,000
  -> FAILED: MemoryError (Out of Memory) at N = 1,000,000,000

Testing limit N = 10,000,000,000
  -> FAILED: MemoryError (Out of Memory) at N = 10,000,000,000

Testing limit N = 100,000,000,000
  -> FAILED: MemoryError (Out of Memory) at N = 100,000,000,000

Testing limit N = 1,000,000,000,000
  -> FAILED: MemoryError (Out of Memory) at N = 1,000,000,000,000

So, I figured I would run this on my Raspberry Pi 5 computer. It allocates enough memory at one billion, but the allocation far exceeds the physical RAM, and on a Raspberry Pi computer, that puts a burden on the MicroSD card. At ten billion, it fails.

username@raspberrypi5:~/prime-number-gfortran-2 $ python3 prime-allocations.py
Testing limit N = 10,000
  -> Allocation successful!
  -> RAM required: 0.08 MB (0.0001 GB)

Testing limit N = 100,000
  -> Allocation successful!
  -> RAM required: 0.76 MB (0.0007 GB)

Testing limit N = 1,000,000
  -> Allocation successful!
  -> RAM required: 7.63 MB (0.0075 GB)

Testing limit N = 10,000,000
  -> Allocation successful!
  -> RAM required: 76.29 MB (0.0745 GB)

Testing limit N = 100,000,000
  -> Allocation successful!
  -> RAM required: 762.94 MB (0.7451 GB)

Testing limit N = 1,000,000,000
  -> Allocation successful!
  -> RAM required: 7629.39 MB (7.4506 GB)

Testing limit N = 10,000,000,000
  -> FAILED: MemoryError (Out of Memory) at N = 10,000,000,000

Testing limit N = 100,000,000,000
  -> FAILED: MemoryError (Out of Memory) at N = 100,000,000,000

Testing limit N = 1,000,000,000,000
  -> FAILED: MemoryError (Out of Memory) at N = 1,000,000,000,000

A $50,000 Reality Check: To put this memory ceiling into perspective, even an enterprise-grade workstation like a System76 Thelio—outfitted with a 96-core AMD Threadripper and 512 GB of DDR5 RAM—would crash trying to execute this naive script for N = 1,000,000,000,000. Python’s dynamic list structure requires roughly 7.45 Terabytes of RAM to hold one trillion elements. The $15 Raspberry Pi Zero 2W doesn’t fail because it is cheap; the script fails because no desktop on Earth has 7.5 TB of continuous system memory.

So, without testing further, I am going to conclude that The Sieve of Eratosthenes has its limitation. But, back at the beginning, I told you that even my Raspberry Pi Zero 2W was processing and had exceeded fifty billion in sixteen days. So, I have something that is working. But I am thinking now that I could even do better.