From 172a03740717796c1a84eb4bfa5455b49a8b56a7 Mon Sep 17 00:00:00 2001 From: tromey Date: Thu, 24 Oct 2002 17:45:23 +0000 Subject: [PATCH] * libjava.lang/Primes.java: Removed. * libjava.lang/Primes.out: Removed. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@58498 138bc75d-0d04-0410-961f-82ee72b054a4 --- libjava/testsuite/ChangeLog | 5 + libjava/testsuite/libjava.lang/Primes.java | 213 ----------------------------- libjava/testsuite/libjava.lang/Primes.out | 51 ------- 3 files changed, 5 insertions(+), 264 deletions(-) delete mode 100644 libjava/testsuite/libjava.lang/Primes.java delete mode 100644 libjava/testsuite/libjava.lang/Primes.out diff --git a/libjava/testsuite/ChangeLog b/libjava/testsuite/ChangeLog index af06d22..18cfe85 100644 --- a/libjava/testsuite/ChangeLog +++ b/libjava/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2002-10-24 Tom Tromey + + * libjava.lang/Primes.java: Removed. + * libjava.lang/Primes.out: Removed. + 2002-10-23 Tom Tromey For PR java/6388: diff --git a/libjava/testsuite/libjava.lang/Primes.java b/libjava/testsuite/libjava.lang/Primes.java deleted file mode 100644 index d6e4336..0000000 --- a/libjava/testsuite/libjava.lang/Primes.java +++ /dev/null @@ -1,213 +0,0 @@ -// 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