Segmented Sieve - Revision history

Admin at 09:27, 20 July 2017

2017-07-20T09:27:15Z

← Older revision		Revision as of 09:27, 20 July 2017
Line 421:		Line 421:

	[[Category:Prime Numbers]]		[[Category:Prime Numbers]]

			[[Category:Number Theory]]

Admin: /* The Subtlety: Starting Points */

2017-07-18T11:23:54Z

The Subtlety: Starting Points

← Older revision		Revision as of 11:23, 18 July 2017
Line 80:		Line 80:

	<math>		<math>
	Q_k = (Q_k – B) \mod p_k		Q_k = (Q_k - B) \mod p_k
	</math>		</math>

Admin: /* The Subtlety: Starting Points */

2017-07-18T11:22:54Z

The Subtlety: Starting Points

← Older revision		Revision as of 11:22, 18 July 2017
Line 74:		Line 74:

	<math>		<math>
	Q_k = - \dfrac{1}{2} \left( L+1+P_{k} \right) \mod ~~P_k~~		Q_k = - \dfrac{1}{2} \left( L+1+p_{k} \right) \mod p_k
	</math>		</math>

Line 80:		Line 80:

	<math>		<math>
	Q_k = (Q_k – B) mod ~~P_k~~		Q_k = (Q_k – B) \mod p_k
	</math>		</math>

			where B denotes the beginning of your block or sub-segment.

	When these formulas are implemented, care must be taken if your language does not handle negative numbers modulo some base (as with Java). If that is the case, you can always multiply by multiples of p, the modular base, to get to a positive number, as in the implementation below:		When these formulas are implemented, care must be taken if your language does not handle negative numbers modulo some base (as with Java). If that is the case, you can always multiply by multiples of p, the modular base, to get to a positive number, as in the implementation below:

Admin: /* The Subtlety: Starting Points */

2017-07-18T11:22:08Z

The Subtlety: Starting Points

← Older revision		Revision as of 11:22, 18 July 2017
Line 77:		Line 77:
	</math>		</math>

	where L is the left-hand side of the interval - the interval starting point.		where L is the left-hand side of the interval - the interval starting point. This can then be reset at the next interval using the formula:

			<math>
			Q_k = (Q_k – B) mod P_k
			</math>

			When these formulas are implemented, care must be taken if your language does not handle negative numbers modulo some base (as with Java). If that is the case, you can always multiply by multiples of p, the modular base, to get to a positive number, as in the implementation below:

	<pre>		<pre>
Line 87:		Line 93:
	}		}
	</pre>		</pre>

			Likewise, here is the Q vector reset function:

	<pre>		<pre>

Admin: /* The Subtlety: Starting Points */

2017-07-18T10:53:45Z

The Subtlety: Starting Points

← Older revision		Revision as of 10:53, 18 July 2017
Line 49:		Line 49:
	But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1000, 1007, 1014, \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1,001</math>.		But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1000, 1007, 1014, \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1,001</math>.

	To generalize this, we can use a formula which forms the core of the segmented sieve algorithm, which I found at [https://programmingpraxis.com/2010/02/05/segmented-sieve-of-eratosthenes/ Pragmatic Programming].		To generalize this, we can use a formula which forms the core of the segmented sieve algorithm, which I found at [https://programmingpraxis.com/2010/02/05/segmented-sieve-of-eratosthenes/ Pragmatic Programming] and verified with [https://rd.springer.com/article/10.1007/BF01932283?no-access=true The Segmented Sieve of Eratosthenes and Primes in Arithmetic Progressions to 10^12].

	We have a set of primes P and are considering integers in a sub-segment, which we will call S. Then we wish to define a vector Q that is the length of the set of primes, and consists of the index at which to begin crossing out factors (that is, it contains the index of the first multiple of that prime).		We have a set of primes P and are considering integers in a sub-segment, which we will call S. Then we wish to define a vector Q that is the length of the set of primes, and consists of the index at which to begin crossing out factors (that is, it contains the index of the first multiple of that prime).

Admin: /* The Subtlety: Starting Points */

2017-07-18T10:52:15Z

The Subtlety: Starting Points

← Older revision		Revision as of 10:52, 18 July 2017
Line 47:		Line 47:
	In other words, let's suppose we're on the step where we want to cross out factors of 7 in our sub-segment. We want to start at some multiple of 7 in the bit vector; then we walk 7 elements and cross out the number at that position; and we repeat that process until we get to the end of the sub-segment.		In other words, let's suppose we're on the step where we want to cross out factors of 7 in our sub-segment. We want to start at some multiple of 7 in the bit vector; then we walk 7 elements and cross out the number at that position; and we repeat that process until we get to the end of the sub-segment.

	But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1,~~000; 1~~,~~007; 1~~,~~014;~~ \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1,001</math>.		But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1000, 1007, 1014, \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1,001</math>.

	To generalize this, we can use a formula which forms the core of the segmented sieve algorithm, which I found at [https://programmingpraxis.com/2010/02/05/segmented-sieve-of-eratosthenes/ Pragmatic Programming].		To generalize this, we can use a formula which forms the core of the segmented sieve algorithm, which I found at [https://programmingpraxis.com/2010/02/05/segmented-sieve-of-eratosthenes/ Pragmatic Programming].
Line 55:		Line 55:
	For example, if we are sieving prime numbers from 100 to 122, then the nearest prime to <math>\sqrt{122}</math> is 13. We use the Sieve of Eratosthenes to generate the set of primes up to 13 (the practical implementation of this will exclude 2 and even numbers from the sieve, so we do that here too):		For example, if we are sieving prime numbers from 100 to 122, then the nearest prime to <math>\sqrt{122}</math> is 13. We use the Sieve of Eratosthenes to generate the set of primes up to 13 (the practical implementation of this will exclude 2 and even numbers from the sieve, so we do that here too):

	<math>P = {3, 5, 7, 11, 13}</math>		<math>P = \{3, 5, 7, 11, 13\}</math>

	The segment we are considering is:		The segment we are considering is:

	<math>		<math>
	S = {101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121}		S = \{101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121\}
	</math>		</math>

Line 66:		Line 66:

	<math>		<math>
	Q = {3, 3, 3, 11, 9}		Q = \{3, 3, 3, 11, 9\}
	</math>		</math>

Admin: /* The Subtlety: Starting Points */

2017-07-18T10:50:21Z

The Subtlety: Starting Points

@@ Line 45: / Line 45: @@
 The algorithm described above is great, but for one thing: how can we determine, quickly, where to begin crossing out factors?
-In other words, let's suppose we're on the step where we want to cross out factors of 7 in our sub-segment. We want to start at some multiple of 7 in the bit vector; then we walk 7 elements and cross out the number at that position; and we repeat that process until we get to the endof the sub-segment.
+In other words, let's suppose we're on the step where we want to cross out factors of 7 in our sub-segment. We want to start at some multiple of 7 in the bit vector; then we walk 7 elements and cross out the number at that position; and we repeat that process until we get to the end of the sub-segment.
 But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1,000; 1,007; 1,014; \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1,001</math>.
-To generalize this, we can use a formula which forms the core of the segmented sieve algorithm:
+To generalize this, we can use a formula which forms the core of the segmented sieve algorithm, which I found at [https://programmingpraxis.com/2010/02/05/segmented-sieve-of-eratosthenes/ Pragmatic Programming].
 <pre>

Admin: /* The Subtlety: Starting Points */

2017-07-18T10:32:28Z

The Subtlety: Starting Points

@@ Line 47: / Line 47: @@
 In other words, let's suppose we're on the step where we want to cross out factors of 7 in our sub-segment. We want to start at some multiple of 7 in the bit vector; then we walk 7 elements and cross out the number at that position; and we repeat that process until we get to the endof the sub-segment.
-But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1,000; 1,007; 1,014; \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1001</math>.
+But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1,000; 1,007; 1,014; \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1,001</math>.
-To generalize this, we can use a formula:
+To generalize this, we can use a formula which forms the core of the segmented sieve algorithm:
 =Code=

Admin: /* The Subtlety: Starting Points */

2017-07-18T10:27:04Z

The Subtlety: Starting Points

← Older revision		Revision as of 10:27, 18 July 2017
Line 43:		Line 43:
	==The Subtlety: Starting Points==		==The Subtlety: Starting Points==

	The algorithm described above is great, but for one thing:		The algorithm described above is great, but for one thing: how can we determine, quickly, where to begin crossing out factors?

			In other words, let's suppose we're on the step where we want to cross out factors of 7 in our sub-segment. We want to start at some multiple of 7 in the bit vector; then we walk 7 elements and cross out the number at that position; and we repeat that process until we get to the endof the sub-segment.

			But finding the start position takes care. If we start at the first number 1,000, we eliminate <math>1,000; 1,007; 1,014; \dots</math>, which are not multiples of 7. In fact, we need to start at 1,001, which is the first multiple of 7 in our sub-segment: <math>7 \times 143 = 1001</math>.

			To generalize this, we can use a formula:

	=Code=		=Code=

Admin at 10:23, 18 July 2017

2017-07-18T10:23:20Z

← Older revision		Revision as of 10:23, 18 July 2017
Line 1:		Line 1:
	This page describes a segmented prime number sieve (i.e., a sieve that can look for prime numbers over an arbitrary interval <math>[M,N]</math>). This is related to [[Project Euler/501]]. Also see [[Sieve of Eratosthenes]].		This page describes a segmented prime number sieve (i.e., a sieve that can look for prime numbers over an arbitrary interval <math>[M,N]</math>). This is related to [[Project Euler/501]]. Also see [[Sieve of Eratosthenes]].

			=Theory=

	==Segmented Prime Sieve==		==Segmented Prime Sieve==
Line 38:		Line 40:

	After running through this process with each prime in the range <math>[2,\sqrt{N}]</math> (optionally stopping when you reach <math>\sqrt{M+S}</math> or the upper boundary of the segment, if the segment is particularly large), the primes can be collected.		After running through this process with each prime in the range <math>[2,\sqrt{N}]</math> (optionally stopping when you reach <math>\sqrt{M+S}</math> or the upper boundary of the segment, if the segment is particularly large), the primes can be collected.

			==The Subtlety: Starting Points==

			The algorithm described above is great, but for one thing:

			=Code=

	==PrimeGenerator Class==		==PrimeGenerator Class==