[转] Java Prime number check

目录 技术

原文出处: http://ventrix.nsdc.gr/code_folds/2008/10/07/java-prime-number/

Information about the author: http://kospol.nsdc.gr/

========================================================================

This is one approach to check if the given number is a prime number. It can take a very big number as an argument. It uses no threads and has no comments. Think it as version 0.01.

/*
 *      Prime.java
 *
 *      Copyright 2008 Ventrix 
 *
 *      http://ventrix.nsdc.gr/code_folds/
 *
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; either version 2 of the License, or
 *      (at your option) any later version.
 *
 *      This program is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 *
 *      You should have received a copy of the GNU General Public License
 *      along with this program; if not, write to the Free Software
 *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 *      MA 02110-1301, USA.
 */  

import java.math.BigInteger;  

public class Prime {  

    private static long start;
    private static long end;  

    public static void main(String[] argv) {
        boolean isprimen;
        //http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html#isProbablePrime(int)
        //http://primes.utm.edu/lists/small/small.html
        //for i in `seq 1 1000`; do java Prime $i >> primes; done
        //cat primes | grep "is a"
        start = System.currentTimeMillis();
        try {
            BigInteger bigNumber = new BigInteger(argv[0]);
            if (bigNumber.compareTo(new BigInteger("2147483647")) == 1) {
                if (bigNumber.compareTo(new BigInteger("9223372036854775807")) == -1) {
                    Long longNumber = new Long(argv[0]);
                    bigNumber = null;
                    isprimen = isNorPrime(longNumber);
                } else {
                    isprimen = isBigPrime(bigNumber);
                }
            } else {
                bigNumber = null;
                Integer intNumber = new Integer(argv[0]);
                isprimen = isPrime(intNumber);
            }  

            if (isprimen) {
                System.out.println(argv[0] + " is a prime!");
            } else {
                System.out.println(argv[0] + " is NOT a prime!");
            }
            end = System.currentTimeMillis();
            System.out.println("Completed in +" + (end - start) + "ms");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }  

    private static boolean isBigPrime(BigInteger number) {
        System.out.println("You gave me a BIG number");
        BigInteger[] remain;
        remain = number.divideAndRemainder(new BigInteger(new Integer("2").toString()));
        if (remain[1].compareTo(new BigInteger("0")) == 0) {
            return false;
        }
        remain = number.divideAndRemainder(new BigInteger(new Integer("3").toString()));
        if (remain[1].compareTo(new BigInteger("0")) == 0) {
            return false;
        }
        int y = 2;
        int x = (int) Math.sqrt(number.doubleValue());
        for (int i = 5; i <= x; i += y, y = 6 - y) {
            remain = number.divideAndRemainder(new BigInteger(new Integer(i).toString()));
            if (remain[1].compareTo(new BigInteger("0")) == 0) {
                return false;
            }
        }
        return true;
    }  

    private static boolean isNorPrime(Long number) {
        System.out.println("You gave me a normal number");
        if (number % 2 == 0) {
            return false;
        }
        if (number % 3 == 0) {
            return false;
        }
        int y = 2;
        int x = (int) Math.sqrt(number);
        for (int i = 5; i <= x; i += y, y = 6 - y) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }  

    private static boolean isPrime(Integer number) {
        System.out.println("You gave me a small number");
        if (number < 2) {
            return false;
        }
        if (number == 2) {
            return true;
        }
        if (number % 2 == 0) {
            return false;
        }
        if (number == 3) {
            return true;
        }
        if (number % 3 == 0) {
            return false;
        }
        int y = 2;
        int x = (int) Math.sqrt(number);
        for (int i = 5; i <= x; i += y, y = 6 - y) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}//class


暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注