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 CommentsShow comments
Problem Recent Solvers52