File Exchange

image thumbnail

Prime numbers

version 1.0.0.0 (1.13 KB) by alexander
Prime number search

1 Download

Updated 26 Mar 2017

View License

searches for all primes up to input "max". I have optimized this as much as I can. Any suggestions on how to increase performance will be appreciated. Looking to get to 1B faster. estimated it would take around 2 hrs on my machine

Cite As

alexander (2020). Prime numbers (https://www.mathworks.com/matlabcentral/fileexchange/62280-prime-numbers), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (3)

Rik

p=true(1,max);
p(1)=false;% 1 is not considered prime
for n=1:floor(max/2)
if ~p(n),continue,end %if already non-prime, skip
p((n*2):n:end)=false; %mark multiples as non-prime
end
p=find(p);

This prime sieve gets to 1B on my machine in under a minute, I didn't test how long your code would take, but it is a lot slower.

alexander

substantial performance increase coming soon. 1B may be back on the table.

alexander

after some more testing I have determined extrapolation is a very bad idea and I cannot predict solution time for larger values. 1B is probably out of the question.

Updates

1.0.0.0

added prime tag

MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux