Problem 1761. Primes Faster for Large N

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is to improve the \"primes\" function for speed. This may be accomplished by fixing memory usage.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Cody appears to have 2GB of RAM based upon \"out of memory\" messages observed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The test case of 2^28 starts to bump into memory limit affects but will complete with the standard primes function.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The reference solution can process N=2^33 on a 16GB machine in 284sec.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> N (max of primes to find)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> vector of primes (all primes less than or equal to N)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring:</w:t></w:r><w:r><w:t> Time to find all primes &lt; 2^28</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Hints:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[1) Doubles use 8 bytes; logicals use 1 byte\n2) The method p = p(p>0); is good but can be improved\n3) The method p = 1:2:n; creates a double and is a little slow\n4) Usage of profiler and Task Manager combined give performance insights]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Related:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1763-primes-for-large-n-2-30-system-memory-limit\"><w:r><w:t>Primes 2^30</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Matlab 2014a incorporated the speed enhancement of logicals</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

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 &lt; 2^28Hints:<pre class="language-matlab">1) Doubles use 8 bytes; logicals use 1 byte
2) The method p = p(p&gt;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
</pre>Related: <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1763-primes-for-large-n-2-30-system-memory-limit">Primes 2^30</a>Matlab 2014a incorporated the speed enhancement of logicals

Solve

Solution Stats

27 Solutions
11 Solvers

Last Solution submitted on Mar 17, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Richard Zapor on 7 Aug 2013

Bart crushed my 2^33 in 284 sec with a time of 92 sec.

Problem Recent Solvers11

Problem Tags

double find logical primes profiler task manager true

Problem 1761. Primes Faster for Large N

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers11

Suggested Problems

More from this Author236

Problem Tags

Problem 1761. Primes Faster for Large N

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers11

Suggested Problems

More from this Author236

Problem Tags

Players