Re: Beginner Projects
- From: Roedy Green <see_website@xxxxxxxxxxxxxxxxxxxx>
- Date: Thu, 30 Aug 2007 03:40:22 GMT
On Wed, 29 Aug 2007 21:23:06 +0000 (UTC), Pseudo Silk Kimono
<Pseudo_Silk_Kimono@xxxxxxxxxxxxx> wrote, quoted or indirectly quoted
someone who said :
I would be eager to hear of any suggested improvments.
Here is my code. I'm the guy who composed the list of projects:
The complete code is posted at
http://mindprod.com/products2.html#PRIMES
/* calculate primes
copyright (c) 1998-2007 Roedy Green, Canadian Mind Products
may be copied and used freely for any purpose but military.
Roedy Green
Canadian Mind Products
#101 - 2536 Wark Street
Victoria, BC Canada
V8T 4G8
tel: (250) 361-9093
mailto:roedyg@xxxxxxxxxxxx
http://mindprod.com
version History
1.1 1998-11-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.
new address and phone.
1.2 2006-01-29 - import to Eclipse and tidy.
1.4 20067-03-06 - reformat with IntelliJ, add Javadoc.
*/
package com.mindprod.primes;
import java.util.BitSet;
/**
* Caluculate primes, and primes near other numbers.
*
* @author Roedy Green, Canadian Mind Products
* @version 1.4, 2006-03-06
*/
class Primes {
// ------------------------------ FIELDS
------------------------------
/**
* not displayed copyright
*/
public static final String EMBEDDEDCOPYRIGHT =
"copyright (c) 1997-2007 Roedy Green, Canadian Mind
Products, http://mindprod.com";;
private static final String RELEASEDATE = "2006-03-06";
/**
* embedded version string.
*/
public static final String VERSIONSTRING = "1.4";
/**
* true for each odd number if is composite
*/
private BitSet b;
/**
* how many elements max in the seize arra
*/
private int sieveCapacity;
// -------------------------- PUBLIC INSTANCE METHODS
--------------------------
/**
* @param candidate number you want to find a prime near.
*
* @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 candidate number you want to find a prime near.
*
* @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
/**
* @param candidate - is this a prime?
*
* @return true if this number is 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 );
}
// --------------------------- CONSTRUCTORS
---------------------------
/**
* 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 );
}
// -------------------------- OTHER METHODS
--------------------------
// biggest number we have computed in our sieve.
// our BitSet array is indexed 0..N (odd only)
/**
* 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
/**
* calculate the sieve, bit map of all primes 0..n
*
* @param n highest number evalutated by the sieve, not
necessarily prime.
*/
private 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
// --------------------------- main() method
---------------------------
/**
* Demonstrate and test the methods
*
* @param args not used
*/
public static void main( String[] args )
{
System.out.println( "primes under 10,000" );
Primes calc = new Primes( 10000 );
int[] primes = calc.getPrimes( 10000 );
for ( int i = 0; i < primes.length; i++ )
{
System.out.println( primes[ i ] );
}
// demonstrate isPrime, above, below
System.out.println( "Is 149 prime? " + calc.isPrime( 149 ) );
System.out
.println( "The prime just below 149 is " + calc.below(
149 ) );
System.out
.println( "The prime just above 149 is " + calc.above(
149 ) );
System.out.println( "Primes just larger than 2^n" );
calc = new Primes( 10000000 );
for ( int pow = 8; pow < 10000000; pow *= 2 )
{
System.out.println( calc.above( pow ) );
}
System.out
.println(
"Validating that isPrime works by comparing it
with brute force successive division." );
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: algorithms give different
answers" );
}
}// end for i
System.out.println( "done" );
}// end main
}// end Primes
--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
.
- References:
- Beginner Projects
- From: Pseudo Silk Kimono
- Beginner Projects
- Prev by Date: Re: Beginner Projects
- Next by Date: Re: Adding SCROLLBARS to a JTextArea
- Previous by thread: Re: Beginner Projects
- Next by thread: Re: Beginner Projects
- Index(es):
Relevant Pages
|
