Sieve of Eratosthenes: Difference between revisions
From charlesreid1
(Created page with "Prime number sieve ==Advanced== See also: Project Euler/Problem 501 The Sieve of Eratosthenes requires O(N) space, so it can be problematic for finding ''very'' large p...") |
No edit summary |
||
| Line 12: | Line 12: | ||
This means M must be larger than the square root of N, however, otherwise we have overlap. | This means M must be larger than the square root of N, however, otherwise we have overlap. | ||
[[Category:Math]] | |||
[[Category:Factoring]] | |||
[[Category:Prime Numbers]] | |||
Revision as of 23:57, 7 July 2017
Prime number sieve
Advanced
See also: Project Euler/Problem 501
The Sieve of Eratosthenes requires O(N) space, so it can be problematic for finding very large prime numbers, larger than a trillion, beyond the working memory of a computer.
In this case we can utilize the segmented Sieve of Eratosthenes algorithm, which generates prime numbers between two numbers m and n.
The savings from implementing a segmented Sieve of Eratosthenes method come from the fact that the amount of space required is only as large as the square root of N, the end point, and that is a substantially smaller storage requirement.
This means M must be larger than the square root of N, however, otherwise we have overlap.