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

Problem 1761. Primes Faster for Large N

Created by Richard Zapor

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

Hints:

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

Tags

Problem Group

Solution Statistics

16 correct solutions 7 incorrect solutions
Last solution submitted on Aug 09, 2013

Problem Comments