diff options
| author | Anthony Green <green@cygnus.com> | 1999-08-09 06:35:56 +0000 |
|---|---|---|
| committer | Anthony Green <green@gcc.gnu.org> | 1999-08-09 06:35:56 +0000 |
| commit | b3967ec43eafa885d2d346c407958151a548fa08 (patch) | |
| tree | 4d94ff9fe054210ba5c1191601149f288de7aee0 /libjava/testsuite | |
| parent | 8d25f6084d5a8180596a0c5ab71b4407e4ddb21f (diff) | |
| download | gcc-b3967ec43eafa885d2d346c407958151a548fa08.zip gcc-b3967ec43eafa885d2d346c407958151a548fa08.tar.gz gcc-b3967ec43eafa885d2d346c407958151a548fa08.tar.bz2 | |
Primes.java: New file.
* libjava.lang/Primes.java: New file.
* libjava.lang/Primes.out: New file.
From-SVN: r28613
Diffstat (limited to 'libjava/testsuite')
| -rw-r--r-- | libjava/testsuite/ChangeLog | 5 | ||||
| -rw-r--r-- | libjava/testsuite/libjava.lang/Primes.java | 213 | ||||
| -rw-r--r-- | libjava/testsuite/libjava.lang/Primes.out | 51 |
3 files changed, 269 insertions, 0 deletions
diff --git a/libjava/testsuite/ChangeLog b/libjava/testsuite/ChangeLog index 49794b1..7b35bc1 100644 --- a/libjava/testsuite/ChangeLog +++ b/libjava/testsuite/ChangeLog @@ -1,3 +1,8 @@ +1999-08-09 Anthony Green <green@cygnus.com> + + * libjava.lang/Primes.java: New file. + * libjava.lang/Primes.out: New file. + 1999-07-31 Alexandre Oliva <oliva@dcc.unicamp.br> * lib/libjava.exp (bytecompile_file): Use `env(SUN_JAVAC)', that diff --git a/libjava/testsuite/libjava.lang/Primes.java b/libjava/testsuite/libjava.lang/Primes.java new file mode 100644 index 0000000..d6e4336 --- /dev/null +++ b/libjava/testsuite/libjava.lang/Primes.java @@ -0,0 +1,213 @@ +// Primes.java
+
+/** Copyright 1998
+ * Roedy Green
+ * Canadian Mind Products
+ * 5317 Barker Avenue
+ * Burnaby, BC Canada V5H 2N6
+ * tel: (604) 435-3016
+ * mailto:roedy@mindprod.com
+ * http://mindprod.com
+ */
+// May be freely distributed for any purpose but military
+
+import java.util.BitSet;
+
+/**
+ * @author Roedy Green
+ * @version 1.10 1998 November 10
+ * Calculate primes using Eratostheses Sieve.
+ * Tell if a given number is prime.
+ * Find a prime just below a given number.
+ * Find a prime just above a given number.
+ */
+
+/*
+ * version 1.1 1998 November 10 - new address and phone.
+ */
+class Primes
+ {
+
+ /**
+ * constructors
+ */
+ Primes()
+ {
+ ensureCapacity(1000);
+ }
+
+ /**
+ * @param capacity - largest number you will be asking if prime.
+ * If give too small a number, it will automatically grow by
+ * recomputing the sieve array.
+ */
+ Primes (int capacity)
+ {
+ ensureCapacity(capacity);
+ }
+
+ /**
+ * @param candidate - is this a prime?
+ */
+ public boolean isPrime(int candidate)
+ {
+ ensureCapacity(candidate);
+ if (candidate < 3) return candidate != 0;
+ if (candidate % 2 == 0 ) return false;
+ return !b.get(candidate/2);
+ }
+
+ /**
+ * @return first prime higher than candidate
+ */
+ public int above(int candidate)
+ {
+ do
+ {
+ // see what we can find in the existing sieve
+ for (int i=candidate+1; i<= sieveCapacity; i++)
+ {
+ if (isPrime(i)) return i;
+ }
+ // Keep building ever bigger sieves till we succeed.
+ // The next prime P' is between P+2 and P^2 - 2.
+ // However that is a rather pessimistic upper bound.
+ // Ideally some theorem would tell us how big we need to build
+ // to find one.
+ ensureCapacity(Math.max(candidate*2, sieveCapacity*2));
+ } // end do
+ while (true);
+ } // end above
+
+ /**
+ * @param return first prime less than candidate
+ */
+ public int below (int candidate)
+ {
+ for (candidate--; candidate > 0; candidate--)
+ {
+ if (isPrime(candidate)) return candidate;
+ }
+ // candidate was 1 or 0 or -ve
+ return 0;
+ }
+
+ /**
+ * calc all primes in the range 1..n,
+ * not the first n primes.
+ * @param n, highest candidate, not necessarily prime.
+ * @return list of primes 1..n in an array
+ */
+ public final int[] getPrimes(int n)
+ {
+ // calculate the primes
+ ensureCapacity(n);
+
+ // pass 1: count primes
+ int countPrimes = 0;
+ for (int i = 0; i <= n; i++)
+ {
+ if (isPrime(i)) countPrimes++;
+ }
+
+ // pass 2: construct array of primes
+ int [] primes = new int[countPrimes];
+ countPrimes = 0;
+ for (int i = 0; i <= n; i++)
+ {
+ if (isPrime(i)) primes[countPrimes++] = i;
+ }
+ return primes;
+ } // end getPrimes
+
+ /**
+ * calculate the sieve, bit map of all primes 0..n
+ * @param n highest number evalutated by the sieve, not necessarily prime.
+ */
+ private final void sieve ( int n )
+ {
+ // Presume BitSet b set is big enough for our purposes.
+ // Presume all even numbers are already marked composite, effectively.
+ // Presume all odd numbers are already marked prime (0 in bit map).
+ int last = (int)(Math.sqrt(n))+1;
+ for (int candidate = 3; candidate <= last; candidate += 2)
+ {
+ // only look at odd numbers
+ if (!b.get(candidate/2) /* if candidate is prime */)
+ {
+ // Our candidate is prime.
+ // Only bother to mark multiples of primes. Others already done.
+ // no need to mark even multiples, already done
+ int incr = candidate*2;
+ for ( int multiple = candidate + incr; multiple < n; multiple += incr)
+ {
+ b.set(multiple/2); // mark multiple as composite
+ } // end for multiple
+ } // end if
+ } // end for candidate
+ // at this point our sieve b is correct, except for 0..2
+ } // end sieve
+
+ /**
+ * Ensure have a sieve to tackle primes as big as n.
+ * If we don't allocate a sieve big enough and calculate it.
+ * @param n - ensure sieve big enough to evaluate n for primality.
+ */
+ private void ensureCapacity (int n)
+ {
+ if ( n > sieveCapacity )
+ {
+ b = new BitSet((n+1)/2);
+ // starts out all 0, presume all numbers prime
+ sieveCapacity = n;
+ sieve(n);
+ }
+ // otherwise existing sieve is fine
+ } // end ensureCapacity
+
+ private int sieveCapacity;
+ // biggest number we have computed in our sieve.
+ // our BitSet array is indexed 0..N (odd only)
+
+ private BitSet b; /* true for each odd number if is composite */
+
+ /**
+ * Demonstrate and test the methods
+ */
+ public static void main (String[] args)
+ {
+ // print primes 1..101
+ Primes calc = new Primes(106);
+ int[] primes = calc.getPrimes(101);
+ for (int i=0; i<primes.length; i++)
+ {
+ System.out.println(primes[i]);
+ }
+
+ // demonstrate isPrime, above, below
+ System.out.println(calc.isPrime(149));
+ System.out.println(calc.below(149));
+ System.out.println(calc.above(149));
+
+ // print all the primes just greater than powers of 2
+ calc = new Primes(10000000);
+ for (int pow=8; pow < 10000000; pow*=2)
+ System.out.println(calc.above(pow));
+
+ // Validate that isPrime works by comparing it with brute force
+ for (int i=3; i<=151; i++)
+ {
+ boolean prime = true;
+ for (int j=2; j<i; j++)
+ {
+ if (i % j == 0 )
+ {
+ prime = false;
+ break;
+ }
+ } // end for j
+ if ( calc.isPrime(i) != prime ) System.out.println(i + " oops");
+ } // end for i
+
+ } // end main
+} // end Primes
diff --git a/libjava/testsuite/libjava.lang/Primes.out b/libjava/testsuite/libjava.lang/Primes.out new file mode 100644 index 0000000..279398b --- /dev/null +++ b/libjava/testsuite/libjava.lang/Primes.out @@ -0,0 +1,51 @@ +1 +2 +3 +5 +7 +11 +13 +17 +19 +23 +29 +31 +37 +41 +43 +47 +53 +59 +61 +67 +71 +73 +79 +83 +89 +97 +101 +true +139 +151 +11 +17 +37 +67 +131 +257 +521 +1031 +2053 +4099 +8209 +16411 +32771 +65537 +131101 +262147 +524309 +1048583 +2097169 +4194319 +8388617 |