"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Thursday, May 6, 2010

A primes generator written in MATLAB

The algorithm below uses the principle of the Sieve of Eratosthenes, only it doesn't start with a set of integers, but rather extends the p array (array of primes) by checking if any successive integer to the seed is divisible by any elements of p - if not, then that integer is a prime and becomes an element of the p array thereby extending it.

Zoom in, in the browser view options for better readibility - I had to leave it small in order to preserve the neat format of the code and the comments.

function y=primelist(n)
p=[2];
%the seed for our primes set
k=1;%array index number
x=1;%denotes the nature of the candidate in the inner loop
i=1;%an arithmetically progressing variable added to failed candidates
   while p(length(p))<n
%p(length(p)) is always the last element of p
     while x==1
     %c will take a 0 value if p(length(p))+i is composite 
     c=floor((p(length(p))+i)/p(k))-((p(length(p)))+i)/p(k);
        if c==0
           x=0;%so a composite will yield x=0
        else if c~=0 && k<length(p)
                k=k+1;
%if not composite try next p element
            else %if c~=0 && k==length(p)
                x=2;% x=2 denotes p(length(p))+i is prime
            end
        end
     end
     if x==0 %&& k<=length(p)
        i=i+1;%hence we try the next successive integer
        x=1;%and hence reset x fo rum the inner loop again
        k=1;%
we start from the first p element again
       else if x==2%once the candidate is verified...
                p=[p (p(length(p))+i)];
%it is adjoined to p
                i=1;
%search starts at next Z after the last prime
                x=1;%x is reset in order to run the inner loop again
                k=1;
%we start from the first p element again
           end
    end
  end%the final output can naturally vary depending on what's desired
p(length(p)-1)%greatest prime smaller than n
%length(p)-1%number of primes up to an including the last one p
%p'%here we get a raw list of primes in the command window
end



Comments and feedback are welcome :)

3 comments:

Zegarnek said...

I have no idea how MATLAB works and actually what MATLAB is... :-(

Mariusz Popieluch said...

Its a very powerful programming language used by mathematicians and engineers.

It's like a very sophisticated calculator, where you program your own functions to churn through repetitive tasks. It has some built in functions, but you can also program stuff from first principles i.e. using loops and boolean statements.

Mariusz Popieluch said...

Since the algorithm I wrote, doesn't use any Matlab specific commands, it is quite universal, which means that it could be translated to any programming language.