001 /*
002 * $Id: PrimeList.java 3497 2011-01-20 21:30:04Z kredel $
003 */
004
005 package edu.jas.arith;
006
007 //import java.util.Random;
008 import java.util.List;
009 import java.util.Iterator;
010 import java.util.ArrayList;
011
012 //import edu.jas.util.StringUtil;
013 import edu.jas.structure.Power;
014
015
016 /**
017 * List of big primes.
018 * Provides an Iterator for generating prime numbers.
019 * Similar to ALDES/SAC2 SACPOL.PRIME list.
020 * @author Heinz Kredel
021 * See Knuth vol 2,page 390, for list of known primes.
022 * See ALDES/SAC2 SACPOL.PRIME
023 */
024
025 public final class PrimeList implements Iterable<java.math.BigInteger> {
026
027
028 /** Range of probable primes.
029 */
030 public static enum Range { small, medium, large, mersenne };
031
032
033 /** The list of probable primes in requested range.
034 */
035 protected final List<java.math.BigInteger> val
036 = new ArrayList<java.math.BigInteger>(50);
037
038
039 /** The last prime in the list.
040 */
041 protected java.math.BigInteger last;
042
043
044 //private final static Random random = new Random();
045
046
047 /**
048 * Constructor for PrimeList.
049 */
050 public PrimeList() {
051 this(Range.medium);
052 }
053
054
055 /**
056 * Constructor for PrimeList.
057 * @param r size range for primes.
058 */
059 public PrimeList(Range r) {
060 // initialize with some known primes, see knuth (2,390)
061 switch( r ) {
062 case small: addSmall();
063 break;
064 default:
065 case medium: addMedium();
066 break;
067 case large: addLarge();
068 break;
069 case mersenne: addMersenne();
070 break;
071 }
072 last = get( size()-1 );
073 }
074
075
076 /**
077 * Add small primes.
078 */
079 private void addSmall() {
080 // really small
081 val.add( new java.math.BigInteger(""+2) );
082 val.add( new java.math.BigInteger(""+3) );
083 val.add( new java.math.BigInteger(""+5) );
084 val.add( new java.math.BigInteger(""+7) );
085 val.add( new java.math.BigInteger(""+11) );
086 val.add( new java.math.BigInteger(""+13) );
087 val.add( new java.math.BigInteger(""+17) );
088 val.add( new java.math.BigInteger(""+19) );
089 val.add( new java.math.BigInteger(""+23) );
090 }
091
092
093 /**
094 * Add medium sized primes.
095 */
096 private void addMedium() {
097 // 2^28-x
098 val.add( getLongPrime(28,57) );
099 val.add( getLongPrime(28,89) );
100 val.add( getLongPrime(28,95) );
101 val.add( getLongPrime(28,119) );
102 val.add( getLongPrime(28,125) );
103 val.add( getLongPrime(28,143) );
104 val.add( getLongPrime(28,165) );
105 val.add( getLongPrime(28,183) );
106 val.add( getLongPrime(28,213) );
107 val.add( getLongPrime(28,273) );
108 // 2^29-x
109 val.add( getLongPrime(29,3) );
110 val.add( getLongPrime(29,33) );
111 val.add( getLongPrime(29,43) );
112 val.add( getLongPrime(29,63) );
113 val.add( getLongPrime(29,73) );
114 val.add( getLongPrime(29,75) );
115 val.add( getLongPrime(29,93) );
116 val.add( getLongPrime(29,99) );
117 val.add( getLongPrime(29,121) );
118 val.add( getLongPrime(29,133) );
119 }
120
121
122 /**
123 * Add large sized primes.
124 */
125 private void addLarge() {
126 // 2^59-x
127 val.add( getLongPrime(59,55) );
128 val.add( getLongPrime(59,99) );
129 val.add( getLongPrime(59,225) );
130 val.add( getLongPrime(59,427) );
131 val.add( getLongPrime(59,517) );
132 val.add( getLongPrime(59,607) );
133 val.add( getLongPrime(59,649) );
134 val.add( getLongPrime(59,687) );
135 val.add( getLongPrime(59,861) );
136 val.add( getLongPrime(59,871) );
137 // 2^60-x
138 val.add( getLongPrime(60,93) );
139 val.add( getLongPrime(60,107) );
140 val.add( getLongPrime(60,173) );
141 val.add( getLongPrime(60,179) );
142 val.add( getLongPrime(60,257) );
143 val.add( getLongPrime(60,279) );
144 val.add( getLongPrime(60,369) );
145 val.add( getLongPrime(60,395) );
146 val.add( getLongPrime(60,399) );
147 val.add( getLongPrime(60,453) );
148 // 2^63-x
149 val.add( getLongPrime(63,25) );
150 val.add( getLongPrime(63,165) );
151 val.add( getLongPrime(63,259) );
152 val.add( getLongPrime(63,301) );
153 val.add( getLongPrime(63,375) );
154 val.add( getLongPrime(63,387) );
155 val.add( getLongPrime(63,391) );
156 val.add( getLongPrime(63,409) );
157 val.add( getLongPrime(63,457) );
158 val.add( getLongPrime(63,471) );
159 }
160
161
162 /**
163 * Add Mersenne sized primes.
164 */
165 private void addMersenne() {
166 // 2^n-1
167 val.add( getMersennePrime(2) );
168 val.add( getMersennePrime(3) );
169 val.add( getMersennePrime(5) );
170 val.add( getMersennePrime(7) );
171 val.add( getMersennePrime(13) );
172 val.add( getMersennePrime(17) );
173 val.add( getMersennePrime(19) );
174 val.add( getMersennePrime(31) );
175 val.add( getMersennePrime(61) );
176 val.add( getMersennePrime(89) );
177 val.add( getMersennePrime(107) );
178 val.add( getMersennePrime(127) );
179 val.add( getMersennePrime(521) );
180 val.add( getMersennePrime(607) );
181 val.add( getMersennePrime(1279) );
182 val.add( getMersennePrime(2203) );
183 val.add( getMersennePrime(2281) );
184 val.add( getMersennePrime(3217) );
185 val.add( getMersennePrime(4253) );
186 val.add( getMersennePrime(4423) );
187 val.add( getMersennePrime(9689) );
188 val.add( getMersennePrime(9941) );
189 val.add( getMersennePrime(11213) );
190 val.add( getMersennePrime(19937) );
191 }
192
193
194 /**
195 * Method to compute a prime as 2**n - m.
196 * @param n power for 2.
197 * @param m for 2**n - m.
198 * @return 2**n - m
199 */
200 public static java.math.BigInteger getLongPrime(int n, int m) {
201 long prime = 2; // knuth (2,390)
202 for ( int i = 1; i < n; i++ ) {
203 prime *= 2;
204 }
205 prime -= m;
206 //System.out.println("p1 = " + prime);
207 return new java.math.BigInteger(""+prime);
208 }
209
210
211 /**
212 * Method to compute a Mersenne prime as 2**n - 1.
213 * @param n power for 2.
214 * @return 2**n - 1
215 */
216 public static java.math.BigInteger getMersennePrime(int n) {
217 BigInteger t = new BigInteger(2);
218 BigInteger p = Power.positivePower(t,n);
219 p = p.subtract(new BigInteger(1));
220 java.math.BigInteger prime = p.getVal();
221 //System.out.println("p1 = " + prime);
222 return prime;
223 }
224
225
226 /**
227 * Check if the list contains really prime numbers.
228 */
229 protected boolean checkPrimes() {
230 return checkPrimes( size() );
231 }
232
233
234 /**
235 * Check if the list contains really prime numbers.
236 */
237 protected boolean checkPrimes(int n) {
238 boolean isPrime;
239 int i = 0;
240 for ( java.math.BigInteger p : val ) {
241 if ( i++ >= n ) {
242 break;
243 }
244 isPrime = p.isProbablePrime(63);
245 if ( !isPrime ) {
246 System.out.println("not prime = " + p);
247 return false;
248 }
249 }
250 return true;
251 }
252
253
254 /**
255 * toString.
256 */
257 @Override
258 public String toString() {
259 return val.toString();
260 }
261
262
263 /**
264 * size of current list.
265 */
266 public int size() {
267 return val.size();
268 }
269
270
271 /**
272 * get prime at index i.
273 */
274 public java.math.BigInteger get(int i) {
275 java.math.BigInteger p;
276 if ( i < size() ) {
277 p = val.get(i);
278 } else {
279 p = last.nextProbablePrime();
280 val.add( p );
281 last = p;
282 }
283 return p;
284 }
285
286
287 /**
288 * Iterator.
289 */
290 public Iterator<java.math.BigInteger> iterator() {
291 return new Iterator<java.math.BigInteger>() {
292 int index = -1;
293 public boolean hasNext() {
294 return true;
295 }
296 public void remove() {
297 throw new UnsupportedOperationException("remove not implemented");
298 }
299 public java.math.BigInteger next() {
300 index++;
301 return get(index);
302 }
303 };
304 }
305
306 }