Problem 1761. Primes Faster for Large N

This Challenge is to improve the "primes" function for speed. This may be accomplished by fixing memory usage.

The Matlab function "primes" has a very efficient sieving method but it suffers from a memory usage issue that may bump into a user's RAM size causing "out of memory", significant slow down, or Matlab freeze.

Cody appears to have 2GB of RAM based upon "out of memory" messages observed.

The test case of 2^28 starts to bump into memory limit affects but will complete with the standard primes function.

The reference solution can process N=2^33 on a 16GB machine in 284sec.

Input: N (max of primes to find)

Output: vector of primes (all primes less than or equal to N)

Scoring: Time to find all primes < 2^28


1) Doubles use 8 bytes; logicals use 1 byte
2) The method p = p(p>0); is good but can be improved
3) The method p = 1:2:n; creates a double and is a little slow
4) Usage of profiler and Task Manager combined give performance insights

Related: Primes 2^30

Matlab 2014a incorporated the speed enhancement of logicals

Solution Stats

72.0% Correct | 28.0% Incorrect
Last solution submitted on Nov 13, 2014

Problem Comments

Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

MATLAB Academy

New to MATLAB?

Learn MATLAB today!

Join the 15-year community celebration.

Play games and win prizes!

Learn more