Java Reference

In-Depth Information

We have to: (1) make sure the invariant is true initially and (2) implement

the English statement “Process
k
”.

1. The invariant is truthified using the assignment
b= p > 1;
—with
k=2
,

the range
2..k-1
is empty.

2. To process
k
means to add
1
to
k
if and only if
k
does not divide
p.

To summarize, always increment
k
, and make
b
false if
k
divides
p
.

This gives us the algorithm of Fig. 7.4.

Optimization

We can make an optimization. Once
b
becomes
false
, it remains
false

because the only statement that changes
b
(after its initialization) is the statement

b=
false
;
. Therefore, it makes sense to terminate the loop if it is recognized that

b
is
false
. We do this by changing the loop condition to:

b&&(k!=p)

We can make another optimization. Suppose an integer
d
divides
p.
Then:

p=d*(p/d)

One of
d
and
p/d
is at most
sqrt(p)
and the other is at least
sqrt(p)
.

Therefore, only the integers in the range
2..floor(sqrt(p))
have to be

checked to see whether they divide
p
. We leave it to you to change the algorithm

to take this into account. Make sure your algorithm evaluates
sqrt(p)
only once.

You will find the functions in class
java.lang.Math
helpful.

7.4.4

A schema for reading

Activity 7-3.4 develops a schema for reading a list of nonzero values from the

Java console and processing them. Activity 7-3.5 uses this schema to print the

sum of a sequence of nonzero values that are read from the Java console.

Activity

7-3.4

//
Set
b
to
"p
is a prime
"

b= p > 1;

int
k= 2;

// {
invariant:
b==(p>1
and no integer in
2..k-1
divides
p) }

while
(k != p) {

if
(p%k==0) {

b=
false
;

}

k= k + 1;

}

// { b = (p > 1
and no integer in
2..p-1
divides
p) }

Figure 7.4:

Testing primality

Search WWH ::

Custom Search