Problem 1763. Primes for Large N: 2^30, System Memory Limit

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 further improve the \"primes\" function for speed/memory usage to the Limit of Cody Memory.</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 memory usage issues, especially on limited memory systems.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1761-primes-faster-for-large-n\"><w:r><w:t>Primes Faster Challenge</w:t></w:r></w:hyperlink><w:r><w:t> gives the first half to maximizing the primes function for optimal memory usage and speed.</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^30 pushes the upper limits of Cody memory.</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^32 on an 8GB machine in 68sec.</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^30</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;\n2) The primes method p(((k*k+1)/2):k:q) creates a vector using q/k*8 bytes. This is 8/3 the size of p for k=3 because k is a double. \n3) Segmentation will keep memory usage below limits at the cost of time.\n4) Cody Available Memory appears to be 537.27MB. XP Operating system eats memory.\n5) Usage of profiler and Task Manager combined give performance insights.]]></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 further improve the "primes" function for speed/memory usage to the Limit of Cody Memory.The Matlab function "primes" has a very efficient sieving method but it suffers from memory usage issues, especially on limited memory systems.The <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1761-primes-faster-for-large-n">Primes Faster Challenge</a> gives the first half to maximizing the primes function for optimal memory usage and speed.Cody appears to have 2GB of RAM based upon "out of memory" messages observed.The test case of 2^30 pushes the upper limits of Cody memory.The reference solution can process N=2^32 on an 8GB machine in 68sec.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^30Hints:<pre class="language-matlab">1) Doubles use 8 bytes;
2) The primes method p(((k*k+1)/2):k:q) creates a vector using q/k*8 bytes. This is 8/3 the size of p for k=3 because k is a double. 
3) Segmentation will keep memory usage below limits at the cost of time.
4) Cody Available Memory appears to be 537.27MB. XP Operating system eats memory.
5) Usage of profiler and Task Manager combined give performance insights.
</pre>

This Challenge is to further improve the "primes" function for speed/memory usage to the Limit of Cody Memory.

The Matlab function "primes" has a very efficient sieving method but it suffers from memory usage issues, especially on limited memory systems.

The <http://www.mathworks.com/matlabcentral/cody/problems/1761-primes-faster-for-large-n Primes Faster Challenge> gives the first half to maximizing the primes function for optimal memory usage and speed.

Cody appears to have 2GB of RAM based upon "out of memory" messages observed.

The test case of 2^30 pushes the upper limits of Cody memory.

The reference solution can process N=2^32 on an 8GB machine in 68sec.

*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^30

*Hints:*

1) Doubles use 8 bytes;
  2) The primes method  p(((k*k+1)/2):k:q) creates a vector using q/k*8 bytes. This is 8/3 the size of p for k=3 because k is a double. 
  3) Segmentation will keep memory usage below limits at the cost of time.
  4) Cody Available Memory appears to be 537.27MB. XP Operating system eats memory.
  5) Usage of profiler and Task Manager combined give performance insights.

Solve

Solution Stats

48 Solutions
13 Solvers

Last Solution submitted on Oct 06, 2021

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Bart on 6 Aug 2013

Nice problem!

I have had some problems to get trough the test suite, one of them was that my primes where in UINT32 and that failed the 'isprime' assertion.

Maybe you could change the following line
pchk=p(ptr);
to
pchk=double(p(ptr));

Richard Zapor on 7 Aug 2013

Double implemented in test suite. Intent is to find the primes, not to get snared by errant function limitations.

Rafael S.T. Vieira on 21 Sep 2020

Currently the MATLAB function primes is able to solve this problem. Since systems always evolve, the problem's author will probably have to be constantly updating it. Or at least, once a year.

Solution Comments

Solution 297267

1 Comment

1 Comment

Richard Zapor on 7 Aug 2013

Nice merger of primes with a customized sieving to set a new speed record on a limited memory system.

Solution 296771

1 Comment

1 Comment

Bart on 5 Aug 2013

Sorry, but can't get code to run at all. So try to get some help this way...

Problem Recent Solvers13

Problem Tags

Community Treasure Hunt

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

Start Hunting!