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

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:* <http://www.mathworks.com/matlabcentral/cody/problems/1763-primes-for-large-n-2-30-system-memory-limit Primes 2^30>

*Matlab 2014a incorporated the speed enhancement of logicals*

Solve

Solution Stats

68 Solutions
45 Solvers

Last Solution submitted on May 12, 2023

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.

Solution Comments

Show comments

Problem Recent Solvers45

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 1761. Primes Faster for Large N

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers45

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Problem 1761. Primes Faster for Large N

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers45

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Players