Find first N primes

Question

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.

• Andy: 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?

Answer 1

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).