Problem:
The Sieve of Eratosthenes is an array of boolean elements whose ith element is true if and
only if i is a prime number. Use the following algorithm to compute and print a sieve of size
1000:
(Precondition: p is an array of n bits.)
(Postcondition: p[i] is true if and only if i is prime.)
You're required to used a java.util.Bitset object.
1. Initialize p[0] and p[1] to be false, and all other p[i] to be true.
2. Repeat step 3 for each i from 3 to n, incrementing by 2.
3. If there is a prime the square root of i that divides i, set p[i] false.
only if i is a prime number. Use the following algorithm to compute and print a sieve of size
1000:
(Precondition: p is an array of n bits.)
(Postcondition: p[i] is true if and only if i is prime.)
You're required to used a java.util.Bitset object.
1. Initialize p[0] and p[1] to be false, and all other p[i] to be true.
2. Repeat step 3 for each i from 3 to n, incrementing by 2.
3. If there is a prime the square root of i that divides i, set p[i] false.
Output:
Figure it out.
Solution:
public class TestSieve { private static final int SIZE=1000; private static BitSet isPrime = new BitSet(SIZE); public static void main(String[] args) { initializeSieve(); ch02.pr20.TestSieve.printSieve(); } private static void initializeSieve() { for (int i = 2; i < SIZE; i++) { isPrime.set(i); } for (int n = 2; 2*n < SIZE; n++) { if (isPrime.get(n)) { for (int m = n; m*n <SIZE; m++) { isPrime.clear(m*n); } } } } private static void printSieve() { int n=0; for (int i = 0; i < SIZE; i++) { if (isPrime.get(i)) { System.out.printf("%5d%s", i, ++n%16==0?"\n":""); } } System.out.printf("%n%d primes less than %d%n", n, SIZE); } }
No comments :
Post a Comment