Prime numbers are extremely useful in cryptography. In fact there are global efforts to find new prime numbers.

By using the sieve of Eratosthenes, we can generate a list of small prime numbers. This algorithm is efficient enough to find all primes less than a million in a matter of seconds. Other methods should be used when seeking larger primes.

Construction

The theory behind this algorithm is to start with a list of all numbers, then to step through the list confirming numbers as prime and crossing out all multiples. The beauty of this algorithm is the way the list of numbers remaining to be checked shrinks at each iteration. In fact after the first iteration we have eliminated half the list, resulting in a highly efficient algorithm.

Below is an implementation of this sieve in GNU Octave. This should work in MATLAB, perhaps requiring minor changes in syntax.

function [list] = primeList (n) 
 
    isPrime = ones(1,n); 
 
    % one is not prime 
    isPrime(1,1) = 0; 
    list = []; 
 
    for i = 2:n 
      if(isPrime(1,i) == 1) 
        list = horzcat(list,i); 
        for j = (i^2):i:n 
          isPrime(1,j) = 0; 
        end 
      end 
    end 
end 

Posted Using LeoFinance ^Beta