1: /* Copyright (C) 2004 Peter Luschny
2: * All rights reserved.
3: *
4: * Permission is hereby granted, free of charge, to any person
5: * obtaining a copy of this software and associated documentation
6: * files ("the Software"), to deal in the Software without
7: * restriction, including without limitation the rights to use,
8: * copy, modify, merge, publish, distribute, sublicense, and / or
9: * sell copies of the Software, and to permit persons to whom
10: * the Software is furnished to do so, subject to the following
11: * conditions:
12: *
13: * The above copyright notice and this permission notice shall be
14: * included in all copies or substantial portions of the Software.
15: */
16:
17: package de.luschny.apps.primes;
18:
19: import static de.luschny.apps.primes.Console.prompt;
20: import static de.luschny.apps.primes.Console.write;
21: import static de.luschny.apps.primes.Console.writeLine;
22: import static java.lang.System.out;
23:
24: import java.io.IOException;
25: import java.util.concurrent.Callable;
26: import java.util.concurrent.ExecutionException;
27: import java.util.concurrent.ExecutorService;
28: import java.util.concurrent.Executors;
29: import java.util.concurrent.Future;
30:
31: import de.luschny.math.arithmetic.Xint;
32: import de.luschny.math.primes.IPrimeCollection;
33: import de.luschny.math.primes.PrimeSieve;
34: import de.luschny.math.util.PositiveRange;
35:
36: /**
37: * <blockquote><pre>
38: * A test and demo suite for de.luschny.math.primes.
39: *
40: * Example demo:
41: * SieveRange is [1, 10.000.000]
42: * NumberOfPrimes is 664579.
43: * Computation in less than 0.3 sec.
44: * </pre></blockquote>
45: *
46: * @author Peter Luschny
47: * @version 2004-10-20
48: */
49:
50: public class SieveTest
51: {
52: static private StopWatch watch;
53: static private PrimeSieve sieve;
54: static private IPrimeCollection primes;
55: static private PositiveRange range;
56: static private int sieveLength;
57:
58: /**
59: * Main - SieveTest
60: *
61: * @param ignored Parameters, if any, will be ignored.
62: */
63:
64: public static void main(String[] ignored)
65: {
66: watch = new StopWatch();
67: openConsole();
68:
69: scanDemo(); prompt();
70: iteratingSubrangeDemo(); prompt();
71:
72: primorialTest(99); prompt();
73: primorialTest(999); prompt();
74:
75: benchmarkTenMillionsDemo(); prompt();
76: nthPrimeDemo(); prompt();
77:
78: sumOfPrimesDemo(); prompt();
79: isPrimeDemo(); prompt();
80:
81: concatenationDemo(); prompt();
82: toArrayDemo(); prompt();
83:
84: saveToFileDemo(); prompt();
85: concurrentExecutionDemo();
86:
87: closeConsole();
88: }
89:
90: /**
91: Scan the full sieve and count primes.
92: */
93:
94: static public void scanDemo()
95: {
96: sieveLength = 111;
97: sieve = new PrimeSieve(sieveLength);
98: primes = sieve.getCollection();
99:
100: writeLine();
101: writeLine("SieveRange is " + primes.getSieveRange());
102: writeLine("NumberOfPrimes " + primes.getNumberOfPrimes());
103:
104: for (int prime : primes)
105: {
106: write(prime + ",");
107: }
108:
109: writeLine();
110: }
111:
112: /**
113: * Working with a subrange of the sieve.
114: */
115:
116: static public void iteratingSubrangeDemo()
117: {
118: range = new PositiveRange(53, 97);
119: primes = sieve.getCollection(range);
120:
121: writeLine();
122: writeLine("SieveRange is " + primes.getSieveRange());
123: writeLine("PrimeRange is " + primes.getPrimeRange());
124: writeLine("NumberOfPrimes " + primes.getNumberOfPrimes());
125:
126: for (int prime : primes)
127: {
128: write(prime + ",");
129: }
130:
131: writeLine();
132: }
133:
134: /**
135: * A small benchmark.
136: */
137:
138: static public void benchmarkTenMillionsDemo()
139: {
140: writeLine();
141:
142: sieveLength = 10000000;
143:
144: watch.clear();
145: watch.start();
146:
147: sieve = new PrimeSieve(sieveLength);
148:
149: watch.stop();
150:
151: primes = sieve.getCollection();
152:
153: writeLine("SieveRange is " + primes.getSieveRange());
154: writeLine("NumberOfPrimes is " + primes.getNumberOfPrimes());
155: writeLine("Computation in " + watch.getSeconds() + " seconds.");
156: }
157:
158: /**
159: * Which is the n-th prime?
160: */
161:
162: static public void nthPrimeDemo()
163: {
164: writeLine();
165:
166: for (int n = 100000; n < 700000; n += 100000)
167: {
168: writeLine("The " + n + "-th prime number is "
169: + sieve.getNthPrime(n));
170: }
171:
172: writeLine();
173: }
174:
175: /**
176: * Which is the sum of the first n primes?
177: */
178:
179: static public void sumOfPrimesDemo()
180: {
181: long sum = 0L;
182: int n = 1;
183:
184: for (int i = 1; i <= 6; i++)
185: {
186: int bound = 100000 * i;
187:
188: write("The sum of the first " + bound
189: + " prime numbers is... ");
190:
191: while (n <= bound)
192: {
193: sum += sieve.getNthPrime(n++);
194: }
195:
196: write(Long.toString(sum));
197: writeLine();
198: }
199: }
200:
201: /**
202: * Individual prime/composite number demo.
203: */
204:
205: static public void isPrimeDemo()
206: {
207: writeLine();
208: writeLine("Individual prime/composite number demo.");
209: writeLine("+ is prime, - is composite.");
210: writeLine();
211:
212: for (int n = 1; n < 33; n++)
213: {
214: write(n + (sieve.isPrime(n) ? "+" : "-") + ", ");
215: }
216:
217: writeLine();
218: }
219:
220: /**
221: * The concatenation property.
222: */
223:
224: static public void concatenationDemo()
225: {
226: int sum = 0;
227:
228: range = new PositiveRange(33, 53);
229: primes = sieve.getCollection(range);
230:
231: writeLine("Range 33..53 : NumberOfPrimes "
232: + primes.getNumberOfPrimes());
233:
234: sum += primes.getNumberOfPrimes();
235: range = new PositiveRange(54, 97);
236: primes = sieve.getCollection(range);
237:
238: writeLine("Range 53..97 : NumberOfPrimes "
239: + primes.getNumberOfPrimes());
240:
241: sum += primes.getNumberOfPrimes();
242: range = new PositiveRange(98, 200);
243: primes = sieve.getCollection(range);
244:
245: writeLine("Range 97..200: NumberOfPrimes "
246: + primes.getNumberOfPrimes());
247:
248: sum += primes.getNumberOfPrimes();
249:
250: writeLine("Sum 33..200: NumberOfPrimes " + sum);
251:
252: range = new PositiveRange(33, 200);
253: primes = sieve.getCollection(range);
254:
255: writeLine("Range 33..200: NumberOfPrimes "
256: + primes.getNumberOfPrimes());
257: }
258:
259: /**
260: * Extract the primes from the sieve as an array.
261: */
262:
263: static public void toArrayDemo()
264: {
265: writeLine();
266: writeLine("Primes between 10 and 33 extracted to an array.");
267: writeLine();
268:
269: primes = sieve.getCollection(10, 33);
270:
271: int[] array = primes.toArray();
272: for (int prime : array)
273: {
274: write(prime + ",");
275: }
276:
277: writeLine();
278: }
279:
280: /**
281: * Save a range of primes to a file.
282: */
283:
284: static public void saveToFileDemo()
285: {
286: writeLine();
287: writeLine("Trying to write primes to file PrimeFile.");
288:
289: primes = sieve.getCollection(77, 777);
290:
291: try {
292: primes.toFile("PrimeFile.dat", IPrimeCollection.PrintOption.CommaSeparated);
293: primes.toFile("PrimeFile.txt", IPrimeCollection.PrintOption.FormattedText);
294: primes.toFile("PrimeFile.xml", IPrimeCollection.PrintOption.Xml);
295: }
296: catch(IOException e)
297: {
298: e.printStackTrace();
299: }
300: writeLine("Success.");
301: writeLine("Look for the files PrimeFile.dat, PrimeFile.txt and PrimeFile.xml!");
302: writeLine();
303: }
304:
305: /**
306: * Primorial-Test.
307: *
308: * @param sieveLength Length of sieve.
309: */
310:
311: static private void primorialTest(int sieveLength)
312: {
313: sieve = new PrimeSieve(sieveLength);
314: primes = sieve.getCollection();
315: Xint p = sieve.getPrimorial(1, sieveLength);
316:
317: writeLine();
318: writeLine("SieveRange is " + primes.getSieveRange());
319: writeLine("NumberOfPrimes " + primes.getNumberOfPrimes());
320: writeLine("A now the primorial of this range.");
321: writeLine(p.toString());
322: writeLine();
323: }
324:
325: /**
326: * Demonstrates that iterating the prime sieve is thread save.
327: */
328: static public void concurrentExecutionDemo()
329: {
330: writeLine("Executing 7 SieveSums concurrently!");
331:
332: int pro = Runtime.getRuntime().availableProcessors();
333: final ExecutorService exe = Executors.newFixedThreadPool(pro);
334:
335: sieveLength = 10000000; // ten million
336: sieve = new PrimeSieve(sieveLength);
337: final IPrimeCollection primes = sieve.getCollection();
338:
339: // Note that we construct all SieveSums with the same
340: // PrimeIteration! This should not end in a mess.
341: Future<Long> sum1 = exe.submit(new SieveSum(primes));
342: Future<Long> sum2 = exe.submit(new SieveSum(primes));
343: Future<Long> sum3 = exe.submit(new SieveSum(primes));
344: Future<Long> sum4 = exe.submit(new SieveSum(primes));
345: Future<Long> sum5 = exe.submit(new SieveSum(primes));
346: Future<Long> sum6 = exe.submit(new SieveSum(primes));
347: Future<Long> sum7 = exe.submit(new SieveSum(primes));
348:
349: try
350: {
351: Long s1 = sum1.get(); Long s2 = sum2.get();
352: Long s3 = sum3.get(); Long s4 = sum4.get();
353: Long s5 = sum5.get(); Long s6 = sum6.get();
354: Long s7 = sum7.get();
355:
356: final long s = 3203324994356L;
357: boolean err = s != s1 || s != s2 || s != s3
358: || s != s4 || s != s5 || s != s6 || s != s7;
359:
360: writeLine(s7 + "," + s6 + ',' + s5 + ',' + s4
361: + ',' + s3 + ',' + s2 + ',' + s1);
362: writeLine(err ? "ERROR! Cannot happen!"
363: : "Yes, PrimeIteration is also thread save ;-)");
364: }
365: catch (InterruptedException e)
366: {
367: e.printStackTrace(out);
368: }
369: catch (ExecutionException e)
370: {
371: e.printStackTrace(out);
372: }
373:
374: prompt();
375: }
376:
377: /**
378: * Writes the banner to the console.
379: */
380: static private void openConsole()
381: {
382: writeLine();
383: writeLine("-----------------------------");
384: writeLine(" *** Welcome To *** ");
385: writeLine(" A Hot Sieve For Cool Primes ");
386: writeLine("-----------------------------");
387: writeLine();
388: }
389:
390: /**
391: * Closes the console.
392: */
393: static private void closeConsole()
394: {
395: writeLine();
396: writeLine();
397: writeLine("** Special thanks to Eratosthenes! **");
398: writeLine("Written by Peter Luschny, 2004-10-20.");
399: writeLine();
400: prompt();
401: }
402:
403: } // endOfSieveTest
404:
405: /**
406: *
407: */
408: final class SieveSum implements Callable<Long>
409: {
410: private final IPrimeCollection primes;
411:
412: /**
413: * @param primes
414: */
415:
416: SieveSum(IPrimeCollection primes)
417: {
418: this.primes = primes;
419: }
420:
421: /**
422: *
423: */
424:
425: public Long call()
426: {
427: long sum = 0L;
428:
429: for (int prime : primes)
430: {
431: sum += prime;
432: }
433:
434: return sum;
435: }
436: }
437:
438: //----------------------------------------------------------
439:
440: class Console {
441:
442: static String PRESSKEY = "Press any key to continue ...";
443:
444: /**
445: * Displays "Press any key to continue ..." and blocks.
446: * input goes to the bit-bucket...
447: */
448:
449: public static void prompt()
450: {
451: write(PRESSKEY);
452:
453: boolean done = false;
454:
455: while (!done)
456: {
457: try
458: {
459: int ch = System.in.read();
460: done = ch < 0 || (char) ch == '\n';
461: }
462: catch (java.io.IOException e)
463: {
464: done = true;
465: }
466:
467: if (!done)
468: {
469: try
470: {
471: Thread.sleep(200);
472: }
473: catch (Exception e)
474: {
475: //
476: }
477: }
478: }
479: }
480:
481: /**
482: * write a string on the console
483: * but don't print a newline.
484: *
485: * @param string the prompt string to display
486: */
487:
488: public static void write(final String string)
489: {
490: System.out.print(string + " ");
491: System.out.flush();
492: }
493:
494: /**
495: * write a string on the console
496: * and output a newline after.
497: *
498: * @param str the string to display
499: */
500:
501: public static void writeLine(final String str)
502: {
503: System.out.println(str);
504: System.out.flush();
505: }
506:
507: /**
508: * outputs a newline.
509: */
510:
511: public static void writeLine()
512: {
513: System.out.println();
514: }
515:
516: } // endOfConsole
517:
518: //----------------------------------------------------------
519:
520: /**
521: * StopWatch.
522: */
523:
524: class StopWatch {
525:
526: private static final String STRING = " sec";
527: private long elapsedCount;
528: private long startCount;
529:
530: /**
531: * Start the time-counter.
532: */
533:
534: public void start()
535: {
536: startCount = System.nanoTime();
537: }
538:
539: /**
540: * Stop the time-counter.
541: */
542:
543: public void stop()
544: {
545: long stopCount = System.nanoTime();
546: elapsedCount += (stopCount - startCount);
547: }
548:
549: /**
550: * Clear the elapsed time-counter.
551: */
552:
553: public void clear()
554: {
555: elapsedCount = 0L;
556: }
557:
558: /**
559: * Get the elapsed time converted to seconds.
560: *
561: * @return Elapsed seconds.
562: */
563:
564: public double getSeconds()
565: {
566: return elapsedCount * 0.000000001; // 10^(-9)
567: }
568:
569: /**
570: * Get the elapsed time as a formated string.
571: *
572: * @return s
573: */
574:
575: @Override
576: public String toString()
577: {
578: return getSeconds() + STRING;
579: }
580: }