1
\$\begingroup\$

Here is code that returns the first N prime numbers:

function [primes] = findFirstNPrimes(N)
    % Accepts an integer, N.
    % Returns the first N primes.

    primes(1) = 2;    % first prime
    i = 3;            % numbers from i and on to be tested 

    while length(primes) <= N
        % 1 x N array of i's, N - current size of: primes
        test = i * ones(1, length(primes));

        % element-by-element modulo division 
        remainder = test - primes .* floor(test ./ primes);

        % if there is a 0 in r, i is not prime.
        isNotPrime = any((remainder == 0));

        % if i is prime, append it to the array of primes
        if (!isNotPrime)
            primes(end + 1) = i;  
        endif  

        % increment, to check next number
        i += 1;
    endwhile  
endfunction    

Input:

p = findFirstNPrimes(20)

Output:

p =
Columns 1 through 17:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
Columns 18 through 21:
61 67 71 73

I would like some recommendation and review regarding:

  1. Octave coding style and conventions. (These are my first steps in Octave.)

  2. Complexity and performance of the code, having in mind most operations performed on arrays.

  3. Readability & any possible improvements.

\$\endgroup\$
  • 1
    \$\begingroup\$ Octave coding style: Use 2 instead of 4 spaces for indentation. Use a space between function calls and opening bracket (for example findFirstNPrimes (N), length (primes) and no space when indexing (this is what you already made but I don't know if knowingly. Btw, I'm sure you knwo there is already a function for getting primes, don't you? \$\endgroup\$ – Andy Aug 30 '17 at 18:04
4
\$\begingroup\$

There are many algorithms that can be used to find the first N primes. I won't comment on the performance of the core algorithm.


Your function returns the first N+1 primes! You must use while length(primes) < N instead of while length(primes) <= N.


You don't need test. You can simply do:

remainder = i - primes .* floor(i ./ primes);

Double negation isn't a good idea: !isNotPrime is a milder version of !isNotUnchecked.

You can do:

isPrime = all(remainder != 0)

Note that I also removed one unnecessary layer of parentheses.


numel is considered to be better than length.


primes is not a good variable name, since it's also the name of the built in function that finds the primes smaller than a given number.


The remainder line is simply: rem(i, primes). (Remember to change the variable name primes).


I like to keep compatibility with MATLAB, for portability purposes. You probably don't have MATLAB now, but you might get it later. You can run almost all MATLAB scripts in Octave (some functions aren't implemented), but not necessarily the other way around.

I'd therefore use i = i + 1, end instead of endif, endwhile and endfunction.

Note: This is a personal preference, and there are definitely people that disagree with me, so it's up to you if you want to follow this advise or not.


Side note:

Initializing firstNPrimes to be zeros(N, 1) and then indexing into it should be faster than this approach. For some reason, my timing shows the opposite for large values of N. I find it strange, but it's a general rule. It has happened once before that tic/toc messes up the timing. I believe that an approach with initializing the vector in front of the loop would be faster, if timed with timeit (not part of Octave currently).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.