Prime Number Research

Abstract

This article aimes to explore methods of computing prime numbers focusing on the optimisation of algorithms. I will also be analysing prime numbers to investigate their distribution, trends and properties.

1. Introduction

1.1 Conditions for prime numbers:

A prime number is a natural number 1, 2, 3… that has exactly two positive divisors: 1 and and the prime its self, therefore primes can only be odd as all even numbers are divisable by 2 meaning that 2 is the only even prime number.


1.2 Why should we study primes computationally?

  • Prime numbers can get very large this makes it inefficent to be handeled manually.
  • Algorithms can find structures and patterns much faster with faster iteration times.
  • Prime numbers are important in security as they are used in cryptography and hashing.

1.3 Main Objectives

  • Generate all of the prime numbers between 1 and n and storing them in a database.
  • Compare time and space complexites of algorithms whilst creating optimisations.
  • Analyse spacing, density, and patterns.
  • Visualise results.

2. Methodology

2.1 Computational Environment

  • Language: Python/Lua for fast iteration
  • Libraries Used: (NumPy , SQlite3, matplotlib)

2.2 Prime Generation Algorithms

2.2.1 Trial Division

Overview

  • This is the most direct aproch to computing prime numbers as it tests whether the number is divisible by any smaller integers.
  • If no other devisor than 1 and itself is found it is is a prime and stored in an array.

Algorithm Description

Given an integer $n$:

  1. If $n \leq 1$, it is not prime and discarded.
  2. Check divisibility from 2 up to $\sqrt{n}$.
  3. If any divisor divides $n$ exactly, then $n$ is composite and therefore not a prime.
  4. Otherwise, $n$ is prime.

Using $\sqrt{n}$ as the upper bound is sufficient here as $n = a * b$, then at least $a$ or $b$ must be less than for equal to $\sqrt{n}$.

Pseudocode

function isPrime(n):
    if n ≤ 1:
        return false

    for i from 2 to floor(√n):
        if n mod i = 0:
            return false
    return true

Optimisations

This algorithms can be optimised by only giving the function odd numbers and 2 this reduces the number of values it has to check by 2.

Conclusion

This algorithm is easy to implement but is too slow to computer primes upto $n=1*10^9$ as it has a worst case time complexity of $O(\sqrt{n})$ this means that it takes increasingly longer to computer larger primes.

2.2.2 Sieve of Eratosthenes

Overview

The Sieve of Eratosthenes is an algorithm that generates all primes upto a limit $n$. This is far more effcient than Trial Division, as instead of testing for each number individually it discards multipules of known primes.

Algorithm Description

Given a limit $(n)$:

  1. Create an array containing all of the natural numbers from 2 to $(n)$, initially marking all numbers as prime.
  2. Starting from 2, mark all multiples of the current number as composite.
  3. Move to the next unmarked number and repeat.
  4. All remaining unmarked numbers are prime.

This can be done using key value pairs or a boolean array

Pseudocode

function sieve(n):
    create array isPrime[0..n] set to true
    isPrime[0] ← false
    isPrime[1] ← false
    for i from 2 to floor(√n):
        if isPrime[i]:
            for j from i*i to n step i:
                isPrime[j] ← false
    return all indices i where isPrime[i] is true

Conclusion

This algorithm is a much better choice than Trial Division as it is $O(n\log{(\log{n})})$ but has $O(n)$ space complexity this means that it is very fast to computer large ranges of primes but has the limitation of memory as the amount fof memory required is proportional $n$