Sieve of Eratosthenes - Revision history

Admin: /* Segmented Sieve Example */

2019-11-23T21:13:03Z

Segmented Sieve Example

← Older revision		Revision as of 21:13, 23 November 2019
Line 43:		Line 43:
	Let's look at a more detailed example.		Let's look at a more detailed example.

	~~====Segmented Sieve Example====~~

	If we are performing the segmented Sieve of Eratosthenes on the interval 100 to 200, we start at 101 (considering odd numbers only), then 103, then 105 - and 105 is divisible by 3. So the Q value for the prime 3 is the number of steps we took to get to that multiple - or, 2.		If we are performing the segmented Sieve of Eratosthenes on the interval 100 to 200, we start at 101 (considering odd numbers only), then 103, then 105 - and 105 is divisible by 3. So the Q value for the prime 3 is the number of steps we took to get to that multiple - or, 2.

Admin: /* Implementation */

2019-11-23T21:12:54Z

Implementation

← Older revision		Revision as of 21:12, 23 November 2019
Line 21:		Line 21:
	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.

	==~~Implementation~~==		==Implementations==

	===Sieve===		===Sieve===
Line 28:		Line 28:

	===Segmented Sieve===		===Segmented Sieve===

			For a more mathy explanation, see [[Segmented Sieve]].

			A words-only explanation:

	The segmented sieve algorithm is structured similarly to the regular sieve - each time, we start with a list of prime numbers up to sqrt(N); then we make multiple passes through the array and eliminate numbers when they are composite.		The segmented sieve algorithm is structured similarly to the regular sieve - each time, we start with a list of prime numbers up to sqrt(N); then we make multiple passes through the array and eliminate numbers when they are composite.
Line 54:		Line 58:

	We are only performing this operation over a relatively short interval - then we collect the results and move on. In the result above, going from 100 to 200, we might perform the above operations in intervals of 10 odd numbers each (covering 20 total numbers, which means we will take 5 steps to cover the whole range of 100 to 200). If we were doing a really big range, like 2 trillion to 3 trillion, we might take steps in intervals of a million.		We are only performing this operation over a relatively short interval - then we collect the results and move on. In the result above, going from 100 to 200, we might perform the above operations in intervals of 10 odd numbers each (covering 20 total numbers, which means we will take 5 steps to cover the whole range of 100 to 200). If we were doing a really big range, like 2 trillion to 3 trillion, we might take steps in intervals of a million.


	==References==		==References==

Admin at 21:05, 23 November 2019

2019-11-23T21:05:22Z

← Older revision		Revision as of 21:05, 23 November 2019
Line 1:		Line 1:
	Prime number sieve		Prime number sieve

	==~~Advanced~~==		==Basic==

			The basic concept behind the Sieve of Eratosthenes is this: create an array of N boolean switches, with switch k indicating that an integer k is prime (on) or composite (off). Starting at switch k, move k switches down, and if it is on, flip it to off (the number is composite because it is divisible by k). In the end, all the switches that are left on are prime numbers. Because of the symmetry of multiplication and factoring, k ranges from 2 to the square root of N.

			Various improvements can be made (e.g., only storing odd numbers), with some improvements leading to surprising performance improvements.



			==Algorithm Analysis==

	See also: [[Project Euler/501]]		See also: [[Project Euler/501]]
Line 13:		Line 21:
	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.

	===~~Implementing~~ Segmented Sieve ~~of Eratosthenes~~===		==Implementation==

			===Sieve===

			See [[Project Euler/501]]

			===Segmented Sieve===

			The segmented sieve algorithm is structured similarly to the regular sieve - each time, we start with a list of prime numbers up to sqrt(N); then we make multiple passes through the array and eliminate numbers when they are composite.

			What's different about the segmented sieve is that we already start at a number M that has some integers as factors, and some integers that are not factors. This changes where we start counting to mark integers as composite.

	~~Implementing~~ a segmented sieve ~~is not much different from implementing the regular method in small steps~~. ~~Each time~~, we start ~~with a list of prime~~ numbers ~~up to sqrt~~(~~N). Next~~, we ~~need a special value called a Q value that indicates~~, ~~for each prime, how far into our sequence (starting at the start index~~) ~~we need to go to get to a number that that prime divides.~~		To illustrate: imagine we are using a segmented sieve to find prime numbers between 1 billion and 2 billion. The segmented sieve might start at 1,000,000,000 or at 1,000,000,001 - and that will change where we should start counting when we consider k = 2 and eliminate all even numbers. (In reality, we would only be considering odd numbers, but this is just an illustrative example.)

	So for example~~, if~~ we are performing the segmented Sieve of Eratosthenes on the interval 100 to 200, we start at 101 (considering odd numbers only), then 103, then 105 - and 105 is divisible by 3. So the Q value for the prime 3 is the number of steps we took to get to that multiple - or, 2.		This offset is a special value called a Q value that indicates, for each prime, how far into our sequence (starting at the start index) we need to go to get to a number that that prime divides.

			Let's look at a more detailed example.

			====Segmented Sieve Example====

			If we are performing the segmented Sieve of Eratosthenes on the interval 100 to 200, we start at 101 (considering odd numbers only), then 103, then 105 - and 105 is divisible by 3. So the Q value for the prime 3 is the number of steps we took to get to that multiple - or, 2.

	Same thing for 5, since 105 is also a multiple of 5, we get a Q value of 2.		Same thing for 5, since 105 is also a multiple of 5, we get a Q value of 2.
Line 29:		Line 53:
	Now, each time we are looking at a segment, we start at that Q value, and we jump forward p units, and eliminate the number p units ahead as a potential factor. For 3, we started with a Q value of 2, so we start at 105. Now we jump ahead 3 units, to 111 (remember we are jumping in intervals of 2, since we are not considering the even numbers). 111 is also divisible by 3, and we can also eliminate it from our list of possible primes.		Now, each time we are looking at a segment, we start at that Q value, and we jump forward p units, and eliminate the number p units ahead as a potential factor. For 3, we started with a Q value of 2, so we start at 105. Now we jump ahead 3 units, to 111 (remember we are jumping in intervals of 2, since we are not considering the even numbers). 111 is also divisible by 3, and we can also eliminate it from our list of possible primes.

	~~Now, we~~ are only performing this operation over a relatively short interval - then we collect the results and move on. In the result above, going from 100 to 200, we might perform the above operations in intervals of 10 odd numbers each (covering 20 total numbers, which means we will take 5 steps to cover the whole range of 100 to 200). If we were doing a really big range, like 2 trillion to 3 trillion, we might take steps in intervals of a million.		We are only performing this operation over a relatively short interval - then we collect the results and move on. In the result above, going from 100 to 200, we might perform the above operations in intervals of 10 odd numbers each (covering 20 total numbers, which means we will take 5 steps to cover the whole range of 100 to 200). If we were doing a really big range, like 2 trillion to 3 trillion, we might take steps in intervals of a million.


	==References==		==References==

Admin: /* Flags */

2017-07-20T09:28:42Z

Flags

← Older revision		Revision as of 09:28, 20 July 2017
Line 42:		Line 42:

	Alternative: https://medium.com/@csnowleopard/project-euler-501-write-up-1fd39a097d03		Alternative: https://medium.com/@csnowleopard/project-euler-501-write-up-1fd39a097d03

			=Related=

			* [[Segmented Sieve]]
			* [[Project Euler]]
			* [[Project Euler/501]]

	=Flags=		=Flags=

Admin at 09:28, 20 July 2017

2017-07-20T09:28:13Z

← Older revision		Revision as of 09:28, 20 July 2017
Line 3:		Line 3:
	==Advanced==		==Advanced==

	See also: [[Project Euler/~~Problem~~ 501]]		See also: [[Project Euler/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.		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.

Admin at 09:27, 20 July 2017

2017-07-20T09:27:51Z

← Older revision		Revision as of 09:27, 20 July 2017
Line 43:		Line 43:
	Alternative: https://medium.com/@csnowleopard/project-euler-501-write-up-1fd39a097d03		Alternative: https://medium.com/@csnowleopard/project-euler-501-write-up-1fd39a097d03

			=Flags=

			{{ProjectEulerFlag}}

	[[Category:Math]]		[[Category:Math]]
	[[Category:Factoring]]		[[Category:Factoring]]
	[[Category:Prime Numbers]]		[[Category:Prime Numbers]]
			[[Category:Number Theory]]

Admin: /* References */

2017-07-08T00:07:08Z

References

← Older revision		Revision as of 00:07, 8 July 2017
Line 34:		Line 34:

	Python implementation of segmented sieve of eratosthenes: http://ideone.com/iHYr1f		Python implementation of segmented sieve of eratosthenes: http://ideone.com/iHYr1f

			Programming Praxis description of algorithm: https://programmingpraxis.com/2010/02/05/segmented-sieve-of-eratosthenes/

			More details and coverage: https://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes#10249801

			Original reference: https://en.wikipedia.org/wiki/Generating_primes

			Alternative: https://medium.com/@csnowleopard/project-euler-501-write-up-1fd39a097d03

Admin at 00:05, 8 July 2017

2017-07-08T00:05:56Z

← Older revision		Revision as of 00:05, 8 July 2017
Line 13:		Line 13:
	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.

			===Implementing Segmented Sieve of Eratosthenes===

			Implementing a segmented sieve is not much different from implementing the regular method in small steps. Each time, we start with a list of prime numbers up to sqrt(N). Next, we need a special value called a Q value that indicates, for each prime, how far into our sequence (starting at the start index) we need to go to get to a number that that prime divides.

			So for example, if we are performing the segmented Sieve of Eratosthenes on the interval 100 to 200, we start at 101 (considering odd numbers only), then 103, then 105 - and 105 is divisible by 3. So the Q value for the prime 3 is the number of steps we took to get to that multiple - or, 2.

			Same thing for 5, since 105 is also a multiple of 5, we get a Q value of 2.

			Likewise with 7, since 105 is also a multiple of 7, we get a Q value of 2.

			For the next prime, 11, the number 121 is a multiple of 11, and 121 is (121-101)/2 = 10 elements down, so we get a Q value of 10.

			And so on.

			Now, each time we are looking at a segment, we start at that Q value, and we jump forward p units, and eliminate the number p units ahead as a potential factor. For 3, we started with a Q value of 2, so we start at 105. Now we jump ahead 3 units, to 111 (remember we are jumping in intervals of 2, since we are not considering the even numbers). 111 is also divisible by 3, and we can also eliminate it from our list of possible primes.

			Now, we are only performing this operation over a relatively short interval - then we collect the results and move on. In the result above, going from 100 to 200, we might perform the above operations in intervals of 10 odd numbers each (covering 20 total numbers, which means we will take 5 steps to cover the whole range of 100 to 200). If we were doing a really big range, like 2 trillion to 3 trillion, we might take steps in intervals of a million.

			==References==

			Python implementation of segmented sieve of eratosthenes: http://ideone.com/iHYr1f

Admin at 23:57, 7 July 2017

2017-07-07T23:57:40Z

← Older revision		Revision as of 23:57, 7 July 2017
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]]

Admin: 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..."

2017-07-07T23:57:18Z

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..."

New page

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.