Friday 20 January 2017

Chapter 22 Exercise 8, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

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.
import java.io.EOFException;
import java.io.IOException;
import java.io.RandomAccessFile;

public class Exercise08 {
 public static void main(String[] args) throws IOException {
  long n = 10_000_000_000L;
  
  RandomAccessFile input = new RandomAccessFile("PrimeNumbers.dat", "rw");

  java.util.List<Long> list = new java.util.ArrayList<>();

  long count = 0; // Count the number of prime numbers
  long number = 2; // A number to be tested for primeness
  int squareRoot = 1; // Check whether number <= squareRoot

  if(input.length() > 0) {
   input.seek(input.length() - 8);
   number = input.readLong() + 1;
   input.seek(0);
   try {
    for (int i = 0; i < 10000; i++) {
     list.add(input.readLong());
    }   
   } catch (EOFException e) {
   } 
   
   squareRoot = (int)(Math.sqrt(number)) + 1;
   count = input.length() / 8;
  }
  

  while (number <= n) {
   boolean isPrime = true;
   if (squareRoot * squareRoot < number)
    squareRoot++;

    while(true) {
    isPrime = true;
    int k;
    for (k = 0; k < list.size() && list.get(k) <= squareRoot; k++) {
     if (number % list.get(k) == 0) {
      isPrime = false;
      break;
     }
    }
    if (input.getFilePointer() == input.length()) {
     break;
    }
    
    if (!isPrime) {
     break;
    } else  {
     list.clear();
     try {
      for (int i = 0; i < 10000; i++) {
       list.add(input.readLong());
      }   
     } catch (EOFException e) {
     }
    }
   }
   
   if (isPrime) {
    count++;
    System.out.println(count + "\t" + number + "\t" + list.size());
    input.writeLong(number);
    list.clear();
    input.seek(0);
    try {
     for (int i = 0; i < 10000; i++) {
      list.add(input.readLong());
     }   
    } catch (EOFException e) {
    } 
   }

   number++;
  }

  System.out.println("\n" + count + " prime(s) less than or equal to " + n);
  input.close();
 }
}

No comments :

Post a Comment