DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 855

/** Compute the distance between two points p1 and p2 */
public static double distance(Point p1, Point p2)

/** Compute the distance between points (x1, y1) and (x2, y2) */
public static double distance( double x1, double y1,
double x2, double y2)

**22.8

( All prime numbers up to 10,000,000,000 ) Write a program that finds
all prime numbers up to 10,000,000,000 . There are approximately
455,052,511 such prime numbers. Your program should meet the following
requirements:

Your program should store the prime numbers in a binary data file, named
PrimeNumbers.dat . When a new prime number is found, the number is
appended to the file.

■

To find whether a new number is prime, your program should load the
prime numbers from the file to an array of the long type of size 10000 .
If no number in the array is a divisor for the new number, continue to read
the next 10000 prime numbers from the data file, until a divisor is found
or all numbers in the file are read. If no divisor is found, the new number
is prime.

■

Since this program takes a long time to finish, you should run it as a batch
job from a UNIX machine. If the machine is shut down and rebooted, your
program should resume by using the prime numbers stored in the binary data
file rather than start over from scratch.

■

**22.9

( Geometry: gift-wrapping algorithm for finding a convex hull ) Section 22.10.1
introduced the gift-wrapping algorithm for finding a convex hull for a set of
points. Assume that the Java's coordinate system is used for the points. Imple-
ment the algorithm using the following method:

/** Return the points that form a convex hull */
public static ArrayList<Point2D> getConvexHull( double [][] s)

Point2D is defined in Section 9.6.

Write a test program that prompts the user to enter the set size and the points
and displays the points that form a convex hull. Here is a sample run:

How many points are in the set? 6
Enter 6 points: 1 2.4 2.5 2 1.5 34.5 5.5 6 6 2.4 5.5 9
The convex hull is
(1.5, 34.5) (5.5, 9.0) (6.0, 2.4) (2.5, 2.0) (1.0, 2.4)

22.10

( Number of prime numbers ) Programming Exercise 22.8 stores the prime num-
bers in a file named PrimeNumbers.dat . Write a program that finds the num-
ber of prime numbers that are less than or equal to 10 , 100 , 1,000 , 10,000 ,
100,000 , 1,000,000 , 10,000,000 , 100,000,000 , 1,000,000,000 , and
10,000,000,000 . Your program should read the data from PrimeNumbers.dat .