93 * Construct a bit sieve of searchLen bits used for finding prime number
94 * candidates. The new sieve begins at the specified base, which must
95 * be even.
96 */
97 BitSieve(BigInteger base, int searchLen) {
98 /*
99 * Candidates are indicated by clear bits in the sieve. As a candidates
100 * nonprimality is calculated, a bit is set in the sieve to eliminate
101 * it. To reduce storage space and increase efficiency, no even numbers
102 * are represented in the sieve (each bit in the sieve represents an
103 * odd number).
104 */
105 bits = new long[(unitIndex(searchLen-1) + 1)];
106 length = searchLen;
107 int start = 0;
108
109 int step = smallSieve.sieveSearch(smallSieve.length, start);
110 int convertedStep = (step *2) + 1;
111
112 // Construct the large sieve at an even offset specified by base
113 MutableBigInteger r = new MutableBigInteger();
114 MutableBigInteger q = new MutableBigInteger();
115 do {
116 // Calculate base mod convertedStep
117 r.copyValue(base.mag);
118 r.divideOneWord(convertedStep, q);
119 start = r.value[r.offset];
120
121 // Take each multiple of step out of sieve
122 start = convertedStep - start;
123 if (start%2 == 0)
124 start += convertedStep;
125 sieveSingle(searchLen, (start-1)/2, convertedStep);
126
127 // Find next prime from small sieve
128 step = smallSieve.sieveSearch(smallSieve.length, step+1);
129 convertedStep = (step *2) + 1;
130 } while (step > 0);
131 }
132
133 /**
134 * Given a bit index return unit index containing it.
135 */
136 private static int unitIndex(int bitIndex) {
137 return bitIndex >>> 6;
138 }
139
|
93 * Construct a bit sieve of searchLen bits used for finding prime number
94 * candidates. The new sieve begins at the specified base, which must
95 * be even.
96 */
97 BitSieve(BigInteger base, int searchLen) {
98 /*
99 * Candidates are indicated by clear bits in the sieve. As a candidates
100 * nonprimality is calculated, a bit is set in the sieve to eliminate
101 * it. To reduce storage space and increase efficiency, no even numbers
102 * are represented in the sieve (each bit in the sieve represents an
103 * odd number).
104 */
105 bits = new long[(unitIndex(searchLen-1) + 1)];
106 length = searchLen;
107 int start = 0;
108
109 int step = smallSieve.sieveSearch(smallSieve.length, start);
110 int convertedStep = (step *2) + 1;
111
112 // Construct the large sieve at an even offset specified by base
113 MutableBigInteger b = new MutableBigInteger(base);
114 MutableBigInteger q = new MutableBigInteger();
115 do {
116 // Calculate base mod convertedStep
117 start = b.divideOneWord(convertedStep, q);
118
119 // Take each multiple of step out of sieve
120 start = convertedStep - start;
121 if (start%2 == 0)
122 start += convertedStep;
123 sieveSingle(searchLen, (start-1)/2, convertedStep);
124
125 // Find next prime from small sieve
126 step = smallSieve.sieveSearch(smallSieve.length, step+1);
127 convertedStep = (step *2) + 1;
128 } while (step > 0);
129 }
130
131 /**
132 * Given a bit index return unit index containing it.
133 */
134 private static int unitIndex(int bitIndex) {
135 return bitIndex >>> 6;
136 }
137
|