MATLAB Prime Number Finder - Project
Report
1. Introduction
This project provides a MATLAB implementation for finding prime numbers using various
algorithms. The goal is to offer a flexible and efficient set of tools for both primality
testing of individual numbers and generating lists of primes within a specified range.
2. Project Structure
• primeFinder.m : The main entry point for the prime number finder. It acts as a
dispatcher, calling the appropriate algorithm based on user input.
• is_prime_trial_division.m : Implements the trial division algorithm for
primality testing.
• sieve_of_eratosthenes.m : Implements the Sieve of Eratosthenes algorithm
for generating primes up to a given limit.
• is_prime_miller_rabin.m : Implements the Miller-Rabin probabilistic primality
test.
• test_prime_finder.m : A unit test script to verify the correctness of the
implemented functions.
• example_usage.m : A script demonstrating how to use the primeFinder
function and its underlying algorithms.
3. Algorithms Implemented
3.1. Trial Division ( is_prime_trial_division.m )
Description: Trial division is the simplest and most intuitive method for primality
testing. To check if a number n is prime, it attempts to divide n by every integer from 2
up to the square root of n . If any of these divisions result in a zero remainder, n is
composite; otherwise, it is prime.
Algorithm Steps: 1. Handle base cases: Numbers less than or equal to 1 are not prime. 2
and 3 are prime. 2. Check divisibility by 2 and 3: If n is divisible by 2 or 3, it's not prime.
3. Iterate from 5: For numbers greater than 3, check divisors of the form 6k ± 1 up to
sqrt(n) . This optimization skips multiples of 2 and 3.
Advantages: Simple to understand and implement, accurate for small numbers.
Disadvantages: Inefficient for large numbers due to its computational complexity.
3.2. Sieve of Eratosthenes ( sieve_of_eratosthenes.m )
Description: The Sieve of Eratosthenes is an ancient algorithm for finding all prime
numbers up to a specified integer. It works by iteratively marking as composite (i.e., not
prime) the multiples of each prime, starting with the first prime number, 2.
Algorithm Steps: 1. Create a boolean list isPrime for numbers from 1 to limit ,
initially marking all as true. 2. Mark 1 as not prime. 3. Iterate from p = 2 up to
sqrt(limit) : a. If p is marked as prime, then all multiples of p (starting from p*p )
are marked as not prime. 4. The numbers remaining marked as true are prime.
Advantages: Very efficient for generating all primes up to a certain limit.
Disadvantages: Requires memory proportional to the limit, which can be an issue for
very large limits.
3.3. Miller-Rabin Primality Test ( is_prime_miller_rabin.m )
Description: The Miller-Rabin test is a probabilistic primality test, meaning it determines
whether a given number is likely prime or definitely composite. It is widely used for
testing large numbers where deterministic primality tests would be too slow.
Algorithm Steps: 1. Handle base cases: Numbers less than 2 are not prime. 2 and 3 are
prime. Even numbers greater than 2 are not prime. 2. Express n-1 as 2^s * d , where
d is an odd integer. 3. Repeat k times (where k is the number of iterations, higher k
means higher accuracy): a. Choose a random integer a in the range [2, n-2] . b.
Compute x = a^d mod n . c. If x = 1 or x = n-1 , then n is likely prime, continue
to the next iteration. d. For r from 1 to s-1 : i. Compute x = x^2 mod n . ii. If x =
n-1 , then n is likely prime, break this inner loop and continue to the next iteration. e. If
none of the above conditions are met, n is composite. 4. If all k iterations pass, n is
considered likely prime.
Advantages: Very efficient for testing the primality of large numbers. Disadvantages:
Probabilistic (may rarely return a composite number as prime, though the probability of
error decreases exponentially with k ).
4. Usage Examples
To use the functions, navigate to the matlab_prime_finder directory in MATLAB and
run the example_usage.m script.
% Example: Check if 29 is prime using Trial Division
isPrime = primeFinder("trialDivision", 29);
disp(["Is 29 prime (Trial Division)? " num2str(isPrime)]);
% Example: Find primes up to 50 using Sieve of Eratosthenes
primesList = primeFinder("sieve", 50);
disp(["Primes up to 50 (Sieve of Eratosthenes): "
num2str(primesList)]);
% Example: Check if 101 is prime using Miller-Rabin test
isPrime = primeFinder("millerRabin", 101);
disp(["Is 101 prime (Miller-Rabin)? " num2str(isPrime)]);
5. Testing
Unit tests are provided in test_prime_finder.m . To run the tests, open MATLAB,
navigate to the project directory, and run the following command in the MATLAB
command window:
runtests("test_prime_finder.m")
This will execute all defined test cases and report any failures or errors.
