Friday July 14, 2000
Quiz 22
1. The logical operator == and the method equals test the same thing?
2. True/False The output from the method countTokens() stays the same no
matter how
many tokens are read.
3. True/False The StringTokenizer class is found in the java.io package.
4. What are two ways we can distinguish a constructor from a regular
method in a class definition?
public class Test {
public static void main(String[] args) {
int a = 3;
double b = a;
System.out.println(b);
}
}
3.0
public class Test1 {
public static void main(String[] args) {
double a = 3.0;
int b = a;
System.out.println(b);
}
}
Test1.java:6: Incompatible type for declaration. Explicit cast needed to
convert double to int.
int b = a;
^
1 error
public class Test2 {
public static void main(String[] args) {
int a = 1/3;
double b = 1/3;
System.out.println(a);
System.out.println(b);
}
}
0
0.0
public class Test3 {
public static void main(String[] args) {
int a = 1/3.0;
System.out.println(a);
}
}
Test3.java:4: Incompatible type for declaration. Explicit cast needed to
convert double to int.
int a = 1/3.0;
^
1 error
Exercise
The Sieve of Eratosthenes
Eratosthenes of Cyrene developed an ingenious method for finding all prime
numbers <= n. The idea is based on the following principle.
Theorem:
If a>1 is a composite number (that is a is not prime), then a has at least one divisor smaller
than or equal to its square root.
Proof:
Suppose a is a composite number. Then a can be written as b*c where b and c are both greater than 1. One of these two
is the larger (unless they are the same number), so let us assume, without loss of generality, that b <= c.
So b*b <= b*c =a. In other words b2 <= a. Since both a and b are positive, this means that b <= square root(a).
Hence, we have demonstrated that if a is a composite number, then it has at least one divisor less than or equal to its square root.
Q.E.D
So if we have a number n and write down all of the number between 2 and n, then successively eliminate all of the numbers
in the list which are multiples of the numbers between 2 and the integer part of the square root of n, then we have eliminated all of
the composite numbers from the list.
Input a number n from the user. Create a file called
Eratosthenes.data. For each number from
2 to n, create a string with the value "y", join these strings by
semicolons and write them to Eratosthenes.data.
For each number, counter, from 2 to the integer portion of the square root
of n do
the following.
For each number, counter1, from counter+1 to n, if counter1 is divisible
by counter, then locate the position in the file Eratosthenes.data
corresponding to counter1 and put the string "n" in that position.
Read the string out of the file Eratosthenes.data and for each position
with a "y" print out that number is prime, otherwise print out that number
is not prime.
A Solution
import java.io.*;
import java.util.*;
public class Write {
// Since we are not going to create an instance of the class Write,
// in order to use a method we will use class methods so that
// we can call them from the main method.
public static void change_string(int n) throws IOException {
// This methods accepts as input the number corresponding to the
// position we wish to change.
// In order to read from a file we must use the two classes
// FileReader and BufferedReader.
FileReader file = new FileReader("Eratosthenes.data");
BufferedReader inputFile = new BufferedReader(file);
// To get a line out of the file we use the readLine()
// method.
String s = inputFile.readLine();
// Since we are done reading from the file we now close it.
inputFile.close();
// We now break the string apart into tokens delimited by a ;.
StringTokenizer myStringTokenizer = new StringTokenizer(s,";");
// We record the total number of tokens found in the string.
int numberOfTokens = myStringTokenizer.countTokens();
// We are going to begin putting the tokens we find back together
// until we come to the token which we want to change. So we read
// the first token from the String and place that into a String
// called output.
String output = myStringTokenizer.nextToken();
// Now we must decide which token we want to replace.
In order to determine this, let us look at the following example string.
Suppose that n is 5. Then the string stored in Eratosthenes.data is
y;y;y;y
Consider the following data.
| # of tokens left (y) |
number corresponding to position of token being read (x) |
| 4 |
2 |
| 3 |
3 |
| 2 |
4 |
| 1 |
5 |
Let us use a couple of these data points to derive a general formula to relate the # of tokens left to the
number corresponding to the position of the token being read.
Two (x,y) pairs are (2,4) and (3,3). The slope of a straight line between these two points is (3-4)/(3-2) = -1. Since the equation of
any non-vertical straight line is y = mx + b, where m is the slope, and (0,b) is the y-intercept. Using our first (x,y) pair, we find
that 4 = -1*2 + b, so that b is 6. So the general equation of the straight line passing between the points (2,4) and (3,3) is y = -x
+ 6.
So this means that y = 6-x. In other words, the # of tokens left is equal to 6 - the number corresponding to the position of the
token being read. Where does 6 come from? Well if we look at our string, we see that 6 is the total number of tokens + 2. So our
relationship is that when we are ready to read a token from the string, the result of countTokens() is equal to the total number of
tokens + 2 - the number corresponding to the position we want to read. So as long as we haven't reached that point, we keep reading
tokens out of the string. We stop when we get to the position of the token we want to change.
while (myStringTokenizer.countTokens() > numberOfTokens-n+2)
output += ";" + myStringTokenizer.nextToken();
output += ";" + "n";
// We now read the token we replaced but don't record it.
s = myStringTokenizer.nextToken();
// Now we go through the rest of the tokens and add them to the
// String output.
while (myStringTokenizer.countTokens() > 0)
output += ";" + myStringTokenizer.nextToken();
// Now we are ready to write the String back to the file so we
// again declare a FileWrite object and a PrintWriter object.
FileWriter file1 = new FileWriter("Eratosthenes.data");
PrintWriter outputFile = new PrintWriter(file1);
// We write the string to the file.
outputFile.println(output);
// We now close the file.
outputFile.close();
}
public static void main(String[] args) throws IOException {
// In order to get input from the user we must use the InputStreamReader
// and BufferedReader classes.
InputStreamReader stream = new InputStreamReader(System.in);
BufferedReader keyboard = new BufferedReader(stream);
System.out.println("Please enter n");
// We now use a wrapper class to turn the String that the user input
// into an int.
int n = new Integer(keyboard.readLine()).intValue();
// Now we set up an output file and prepare it to be written to. We
// use the FileWriter and PrintWriter classes.
FileWriter file = new FileWriter("Eratosthenes.data");
PrintWriter outputFile = new PrintWriter(file);
// We initialize our output String with a beginning "y".
String output = "y";
// Now we add in "y"s corresponding to all numbers up to n.
for (int counter=3;counter<=n;counter++)
output += ";" + "y";
// Now we write the String to our output file.
outputFile.println(output);
// Now we close the output file.
outputFile.close();
// We now set up two loops. The outer loop will go from 2 to the
// integer portion of the square root of n. The inner loop will
// go from counter+1 to n. If the counter variable in the inner
// for loop has a zero remainder when we divide it by the counter
// variable in the outer for loop, when we then change the string
// in the position corresponding to the counter variable in the inner
// loop in the String stored in Eratosthenes.data to an "n".
for (int counter=2;counter<=(int)(Math.sqrt(n));counter++)
for (int counter1=counter+1;counter1<=n;counter1++)
if (counter1 % counter == 0)
Write.change_string(counter1);
// Now that the string is set up, we read it from the file, and
// tokenize it. For each token we get to, if it is a "y" we report
// that the number corresponding to that position is a prime
// number. Otherwise we report that the number corresponding to
// that position is not a prime number.
FileReader file1 = new FileReader("Eratosthenes.data");
BufferedReader inputFile = new BufferedReader(file1);
String s = inputFile.readLine();
StringTokenizer myStringTokenizer = new StringTokenizer(s,";");
int counter = 2;
while (myStringTokenizer.countTokens() > 0)
if (myStringTokenizer.nextToken().equals("y"))
System.out.println(counter++ + " is prime.");
else
System.out.println(counter++ + " is not prime.");
}
}
Write.java