Problem 2337. Sum of big primes without primes

Created by Jean-Marie Sainthillier

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>Inspired by Project Euler n°10 (I am quite obviously a fan).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>With problem n°250 by Doug, you can find some global methods to compute the sum of all the primes below the input n.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, the sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>But how to proceed (in time) with big number and WITHOUT the primes function ?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>HINTS: sum(primes(n)) is possible here but why miss the wonderfull Sieve of Eratosthenes ?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes\"><w:r><w:t>http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes</w:t></w:r></w:hyperlink></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>"}]}

Solve

Solution Stats

125 Solutions
78 Solvers

Last Solution submitted on Aug 09, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Rafael S.T. Vieira on 8 Aug 2020 at 5:06

Be careful, I've implemented the sieve, but not all versions of it are sufficiently fast to handle the biggest numbers in the test suite.

Solution Comments

Solution 447945

2 Comments

2 Comments

Jon on 30 May 2014

This doesn't use primes(x),but still feels a little like cheating.

Rafael S.T. Vieira on 8 Aug 2020 at 4:23

The whole point of using the sieve is not knowing which numbers are prime. So it is no different than sum(primes).

Problem Recent Solvers78

Problem Tags

eratosthenes primes project euler

Problem 2337. Sum of big primes without primes

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers78

Suggested Problems

More from this Author43

Problem Tags

Problem 2337. Sum of big primes without primes

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers78

Suggested Problems

More from this Author43

Problem Tags

Players