Java Create a program that generates a file of all the prime numbers less than a

Question

Java

Create a program that generates a file of all the prime numbers less than a number N taken from command line. It is up to you how you store this data into the file as long as the next part can read it. Your program should work for numbers up to 100,000. You must implement the Sieve of Eratosthenes in order to generate this file.

Example input: 10

Example output in ‘‘file.txt’’:

2 3 5 7 2

Part 2 Create a program that takes a file of prime numbers generated from Part 1 and stores them in any way of your choosing. The user may query the program as many times as they would like and it will output whether or not the number given is prime. The queries must run in log(n) time where n is the amount of prime numbers in the file. If the number that is entered is negative stop the program. If the number is greater than the largest in the file inform the user that they need a file which contains more prime numbers.

Example input in ‘‘file.txt’’:

2 3 5 7

Example command line interaction with user:

Enter a number.

3

3 is a prime number.

Enter another number. 4

4 is not a prime number.

Enter another number.

8

Current file not large enough for 8.

Enter another number.

-1

Bye

Explanation / Answer

import java.io.*;
import java.util.*;
import java.util.Scanner;

class Eratosthenes {

    static int countPrimesUpperBound(int max) {
        return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
    }
    // Return primes less than limit
    static void generatePrimes(int limit) throws IOException{
        FileOutputStream out = null;
        final int numPrimes = countPrimesUpperBound(limit);
        ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
        boolean [] isComposite    = new boolean [limit];   // all false
        final int sqrtLimit       = (int)Math.sqrt(limit); // floor
        for (int i = 2; i <= sqrtLimit; i++) {
            if (!isComposite [i]) {
                primes.add(i);
                for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                    isComposite [j] = true;
            }
        }
        for (int i = sqrtLimit + 1; i < limit; i++)
            if (!isComposite [i])
                primes.add(i);

        try {
             out = new FileOutputStream("file.txt");
             for (int c : primes)
                out.write(c);
          }finally {
             if (out != null) {
                out.close();
             }
          }
    }

    public static void main (String[] args) throws IOException
    {
        FileReader in = null;
        // InputStreamReader cin = null;

        generatePrimes(15);

        ArrayList<Integer> primes = new ArrayList<Integer>();
        int maxPrime = 0;
        try {
            in = new FileReader("file.txt");
            int c;

            while ((c = in.read()) != -1) {
                primes.add(c);
                maxPrime =c;
            }
        } finally {
            if (in != null) {
                in.close();
            }
        }
        // System.out.println(primes.toString() + " maxPrime is: " + maxPrime);

        // cin = new InputStreamReader(System.in);
        Scanner cin = new Scanner(System.in);
        System.out.println("Enter a number ");
        int c;
        do {
            c = cin.nextInt();
            // System.out.print(c);
            if(c>maxPrime){
                System.out.println("Current file not large enough for "+c);
            } else if (c==-1){
                System.out.println("Bye");
                break;
            } else {
                if(primes.contains(c)){
                    System.out.println(c+" is a Prime number");
                } else {
                    System.out.println(c+" is not a Prime number");
                }
            }
        } while(c != 'q');

    }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.