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

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

Solution Stats

85.0% Correct | 15.0% Incorrect
Last Solution submitted on Apr 02, 2024

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers53

Suggested Problems

More from this Author304

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!