Tuesday 14 March 2017

java program for prime number

import java.math.BigInteger;
import java.util.Random;

public class PrimeEx {

    /**
     * @param args
     */
    public static void main(String[] args) {
        printTest(10, 4);
        printTest(2, 2);
        printTest(54161329, 4);
        printTest(1882341361, 2);
        printTest(36, 9);

        System.out.println(isPrime(54161329) + " expect false");
        System.out.println(isPrime(1882341361) + " expect true");
        System.out.println(isPrime(2) + " expect true");
        int numPrimes = 0;
        Stopwatch s = new Stopwatch();
        s.start();
        for(int i = 2; i < 10000000; i++) {
            if(isPrime(i)) {
                numPrimes++;
            }
        }
        s.stop();
        System.out.println(numPrimes + " " + s);
        s.start();
        boolean[] primes = getPrimes(10000000);
        int np = 0;
        for(boolean b : primes)
            if(b)
                np++;
        s.stop();
        System.out.println(np + " " + s);

        System.out.println(new BigInteger(1024, 10, new Random()));
    }

    public static boolean[] getPrimes(int max) {
        boolean[] result = new boolean[max + 1];
        for(int i = 2; i < result.length; i++)
            result[i] = true;
        final double LIMIT = Math.sqrt(max);
        for(int i = 2; i <= LIMIT; i++) {
            if(result[i]) {
                int index = 2 * i;
                while(index < result.length){
                    result[index] = false;
                     index += i;
                }
            }
        }
        return result;
    }


    public static void printTest(int num, int expectedFactors) {
        Stopwatch st = new Stopwatch();
        st.start();
        int actualFactors = numFactors(num);
        st.stop();
        System.out.println("Testing " + num + " expect " + expectedFactors + ", " +
                "actual " + actualFactors);
        if(actualFactors == expectedFactors)
            System.out.println("PASSED");
        else
            System.out.println("FAILED");
        System.out.println(st.time());
    }

    // pre: num >= 2
    public static boolean isPrime(int num) {
        assert num >= 2 : "failed precondition. num must be >= 2. num: " + num;
        final double LIMIT = Math.sqrt(num);
        boolean isPrime = (num == 2) ? true : num % 2 != 0;
        int div = 3;
        while(div <= LIMIT && isPrime) {
            isPrime = num % div != 0;
            div += 2;
        }
        return isPrime;
    }

     public static int numFactors(int num) {
        assert num >= 2 : "failed precondition. num must be >= 2. num: " + num;
        int result = 0;
        final double SQRT = Math.sqrt(num);
        for(int i = 1; i < SQRT; i++) {
            if(num % i == 0) {
                result += 2;
            }
        }
        if(num % SQRT == 0)
            result++;
        return result;
    }

}


No comments:

Post a Comment