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

74.07% Correct | 25.93% Incorrect
Last Solution submitted on Mar 17, 2020

Problem Comments