代码之家  ›  专栏  ›  技术社区  ›  Anantha Kumaran

Java中最原始的测试方法是什么?

  •  47
  • Anantha Kumaran  · 技术社区  · 15 年前

    我试图找到最快的方法来检查给定的数字是否是(Java)。下面是我提出的几种素性测试方法。有没有比第二个实现(isprime2)更好的方法?

        public class Prime {
    
            public static boolean isPrime1(int n) {
                if (n <= 1) {
                    return false;
                }
                if (n == 2) {
                    return true;
                }
                for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
                    if (n % i == 0) {
                        return false;
                    }
                }
                return true;
            }
            public static boolean isPrime2(int n) {
                if (n <= 1) {
                    return false;
                }
                if (n == 2) {
                    return true;
                }
                if (n % 2 == 0) {
                    return false;
                }
                for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
                    if (n % i == 0) {
                        return false;
                    }
                }
                return true;
            }
        }
    
    
    
    public class PrimeTest {
    
        public PrimeTest() {
        }
    
        @Test
        public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
    
            Prime prime = new Prime();
            TreeMap<Long, String> methodMap = new TreeMap<Long, String>();
    
    
            for (Method method : Prime.class.getDeclaredMethods()) {
    
                long startTime = System.currentTimeMillis();
    
                int primeCount = 0;
                for (int i = 0; i < 1000000; i++) {
                    if ((Boolean) method.invoke(prime, i)) {
                        primeCount++;
                    }
                }
    
                long endTime = System.currentTimeMillis();
    
                Assert.assertEquals(method.getName() + " failed ", 78498, primeCount);
                methodMap.put(endTime - startTime, method.getName());
            }
    
    
            for (Entry<Long, String> entry : methodMap.entrySet()) {
                System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds ");
            }
        }
    }
    
    14 回复  |  直到 6 年前
        1
  •  68
  •   Bart Kiers    14 年前

    另一种方法是:

    boolean isPrime(long n) {
        if(n < 2) return false;
        if(n == 2 || n == 3) return true;
        if(n%2 == 0 || n%3 == 0) return false;
        long sqrtN = (long)Math.sqrt(n)+1;
        for(long i = 6L; i <= sqrtN; i += 6) {
            if(n%(i-1) == 0 || n%(i+1) == 0) return false;
        }
        return true;
    }
    

    BigInteger's isProbablePrime(...) 对所有32位都有效 int s。

    编辑

    注意 isProbablePrime(certainty) 不总是给出正确的答案。当确定性处于低位时,它会产生误报,正如评论中提到的@dimo414。

    不幸的是,我找不到声称 isrobableprime(确定性) 对所有人都有效(32位) int (有足够的把握!)。

    所以我做了几个测试。我创造了一个 BitSet 尺寸的 Integer.MAX_VALUE/2 表示所有不均匀数,并使用质数筛查找范围内的所有质数 1..Integer.MAX_VALUE . 然后我从 i=1..Integer.MAX_VALUE 测试每一个 new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i) .

    对于确定性5和10, isProbablePrime(...) 在整个过程中产生了误报。但与 isProbablePrime(15) ,没有测试失败。

    这是我的试验台:

    import java.math.BigInteger;
    import java.util.BitSet;
    
    public class Main {
    
        static BitSet primes;
    
        static boolean isPrime(int p) {
            return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
        }
    
        static void generatePrimesUpTo(int n) {
            primes = new BitSet(n/2);
    
            for(int i = 0; i < primes.size(); i++) {
                primes.set(i, true);
            }
    
            primes.set(0, false);
            int stop = (int)Math.sqrt(n) + 1;
            int percentageDone = 0, previousPercentageDone = 0;
            System.out.println("generating primes...");
            long start = System.currentTimeMillis();
    
            for(int i = 0; i <= stop; i++) {
                previousPercentageDone = percentageDone;
                percentageDone = (int)((i + 1.0) / (stop / 100.0));
    
                if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
                    System.out.println(percentageDone + "%");
                }
    
                if(primes.get(i)) {
                    int number = (i * 2) + 1;
    
                    for(int p = number * 2; p < n; p += number) {
                        if(p < 0) break; // overflow
                        if(p%2 == 0) continue;
                        primes.set(p/2, false);
                    }
                }
            }
            long elapsed = System.currentTimeMillis() - start;
            System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
        }
    
        private static void test(final int certainty, final int n) {
            int percentageDone = 0, previousPercentageDone = 0;
            long start = System.currentTimeMillis();
            System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
            for(int i = 1; i < n; i++) {
                previousPercentageDone = percentageDone;
                percentageDone = (int)((i + 1.0) / (n / 100.0));
                if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
                    System.out.println(percentageDone + "%");
                }
                BigInteger bigInt = new BigInteger(String.valueOf(i));
                boolean bigIntSays = bigInt.isProbablePrime(certainty);
                if(isPrime(i) != bigIntSays) {
                    System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
                        + bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
                        " a prime");
                    return;
                }
            }
            long elapsed = System.currentTimeMillis() - start;
            System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
                    " minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
        }
    
        public static void main(String[] args) {
            int certainty = Integer.parseInt(args[0]);
            int n = Integer.MAX_VALUE;
            generatePrimesUpTo(n);
            test(certainty, n);
        }
    }
    

    我跑来跑去:

    java -Xmx1024m -cp . Main 15
    

    在我的机器上产生质数需要30秒。对所有人的真正考验 i 在里面 1..integer.max_值 花了大约2小时15分钟。

        2
  •  43
  •   user102008    14 年前

    这是最优雅的方式:

    public static boolean isPrime(int n) {
        return !new String(new char[n]).matches(".?|(..+?)\\1+");
    }
    

    Java 1.4 +。不需要进口。

    那么短。如此美丽。

        3
  •  12
  •   zx485 potemkin    9 年前

    看看 AKS primality test (以及各种优化)。它是一个在多项式时间内运行的确定性素性测试。

    Java中有一个算法的实现。 from the University of Tuebingen (Germany) here

        4
  •  10
  •   Joe    9 年前

    你迈出了消除2的所有倍数的第一步。

    但是,你为什么停在那里?你可以消除除3以外的所有3的倍数,除5以外的所有5的倍数,等等。

    当你按照这个推理得出结论时,你会得到 Sieve of Eratosthenes

        5
  •  4
  •   saugata    15 年前

    如果你只是想找出一个数是否是素数,那就足够了,但是如果你想找出从0到n的所有素数,一个更好的选择是 Sieve of Eratosthenes

    但这将取决于Java对数组大小的限制等。

        6
  •  4
  •   Andrew Clear    13 年前

    你的算法对相当小的数字很有效。对于大数,应使用高级算法(例如基于椭圆曲线)。另一个想法是使用一些“pseuso素数”测试。这将很快证明一个数字是一个素数,但它们并不是100%准确。但是,它们可以帮助你比你的算法更快地排除一些数字。

    最后,尽管编译器可能会为您优化此功能,但您应该编写:

    int max =  (int) (Math.sqrt(n) + 1);
    for (int i = 3; i <= max; i = i + 2) {
    }
    
        7
  •  3
  •   Kannan Ekanath    15 年前

    你所写的是最普通的程序员所做的,而且大部分时间应该足够了。

    然而,如果你追求的是“最佳科学算法”,那么有许多不同的变化(具有不同的确定性水平)被记录在案 http://en.wikipedia.org/wiki/Prime_number .

    例如,如果您有一个70位数字,jvm的物理限制可能会阻止您的代码运行,在这种情况下,您可以使用“筛子”等。

    再说一遍,就像我说的,如果这是一个编程问题或是软件使用的一般问题,你的代码应该是完美的:)

        8
  •  3
  •   Aurril Thorbjørn Ravn Andersen    15 年前

    根据需要测试的数字的长度,如果要求的数字在此范围内,则可以为较小的值(n<10^6)预计算质数列表,该列表将首先使用。这当然是最快的方法。 就像在其他答案中提到的 Sieve of Eratosthenes 是生成此类预计算列表的首选方法。

    如果你的数字大于这个数,你可以使用拉宾的素性检验。 Rabin primality test

        9
  •  3
  •   Ariful Islam    8 年前

    我认为这种方法是最好的。至少对我来说-

        public static boolean isPrime(int num)
        {
            for (int i = 2; i<= num/i; i++)
            {
                if (num % i == 0)
                {
                    return false;
                }
            }
            return num > 1;
        }
    
        10
  •  3
  •   Charles    8 年前

    由于JAISCHKE(1993)的快速测试是Miller Rabin测试的确定版本,它没有假阳性低于4759123141,因此可以应用于Java。 int S。

    // Given a positive number n, find the largest number m such
    // that 2^m divides n.
    private static int val2(int n) {
      int m = 0;
      if ((n&0xffff) == 0) {
        n >>= 16;
        m += 16;
      }
      if ((n&0xff) == 0) {
        n >>= 8;
        m += 8;
      }
      if ((n&0xf) == 0) {
        n >>= 4;
        m += 4;
      }
      if ((n&0x3) == 0) {
        n >>= 2;
        m += 2;
      }
      if (n > 1) {
        m++
      }
      return m;
    }
    
    // For convenience, handle modular exponentiation via BigInteger.
    private static int modPow(int base, int exponent, int m) {
      BigInteger bigB = BigInteger.valueOf(base);
      BigInteger bigE = BigInteger.valueOf(exponent);
      BigInteger bigM = BigInteger.valueOf(m);
      BigInteger bigR = bigB.modPow(bigE, bigM);
      return bigR.intValue();
    }
    
    // Basic implementation.
    private static boolean isStrongProbablePrime(int n, int base) {
      int s = val2(n-1);
      int d = modPow(b, n>>s, n);
      if (d == 1) {
        return true;
      }
      for (int i=1; i < s; i++) {
        if (d+1 == n) {
          return true;
        }
        d = d*d % n;
      }
      return d+1 == n;
    }
    
    public static boolean isPrime(int n) {
      if ((n&1) == 0) {
        return n == 2;
      }
      if (n < 9) {
        return n > 1;
      }
    
      return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61);
    }
    

    这不适合 long 变量,但另一个测试会:bpsw测试没有高达2^64的反例。这基本上包括一个2-强的或然素数检验,如上文所述,然后是一个强的lucas检验,这个检验有点复杂,但没有本质上的不同。

    这两种测试都比任何一种试验部门都要快得多。

        11
  •  2
  •   Ash Pera    8 年前

    当然,素性测试有上百种,根据数量大小、特殊形式、因子大小等各有利弊。

    然而,在Java中,我发现最有用的是:

    BigInteger.valueOf(long/int num).isProbablePrime(int certainty);
    

    它已经实现了,而且速度相当快(我发现一个1000x1000的矩阵需要大约6秒的时间来填充long02^64和确定的15),而且可能比我们人类能想到的任何东西都要优化。

    它使用了 Baillie–PSW primality test ,没有已知的反例。(尽管它可能使用稍弱的测试版本,有时可能会出错。也许)

        12
  •  1
  •   HiBrian    8 年前

    我在这里优化了试验部门: 它返回一个布尔值。 除isprime(n)外,还需要其他方法。

        static boolean[] smlprime = {false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false};
    
    public static boolean isPrime(long n) { //optimised
        if (n < 2) {
            return false;
        }
        if (n < smlprime.length) //less than smlprime.length do not need to be checked
        {
            return smlprime[(int) n]; //lol already checked
        }
    
        long[] dgt = longDigits(n);
        long ones = dgt[dgt.length - 1];
        if (ones % 2 == 0) {
            return false;
        }
        if (ones == 0 || ones == 5) {
            return false;
        }
        if (digitadd(n) % 3 == 0) {
            return false;
        }
        if (n % 7 == 0) {
            return false;
        }
        if (Square(n)) {
            return false;
        }
        long hf = (long) Math.sqrt(n);
        for (long j = 11; j < hf; j = nextProbablePrime(j)) {
            //System.out.prlongln(Math.sqrt(i));
            if (n % j == 0) {
                return false;
            }
            //System.out.prlongln("res"+res);
        }
        return true;
    }
    
    public static long nextProbablePrime(long n) {
        for (long i = n;; i++) {
            if (i % 2 != 0 && i % 3 != 0 && i % 7 != 0) {
                return i;
            }
        }
    }
    
    public static boolean Square(long n) {
        long root = (long) Math.sqrt(n);
        return root * root == n;
    }
    
    public static long[] longDigits(long n) {
        String[] a = Long.toString(n).split("(?!^)");
        long[] out = new long[a.length];
        for (int i = 0; i < a.length; i++) {
            out[i] = Long.parseLong(a[i]);
        }
        return out;
    }
    
    public static long digitadd(long n) {
        long[] dgts = longDigits(n);
        long ans = 0;
        for (long i : dgts) {
            ans += i;
        }
        return ans;
    }
    
        13
  •  1
  •   Radiodef    7 年前

    算法效率:o(n^(1/2))算法

    注意:下面的示例代码包含计数变量和对打印函数的调用,以便打印结果:

    import java.util.*;
    
    class Primality{
        private static void printStats(int count, int n, boolean isPrime) {
    
            System.err.println( "Performed " + count + " checks, determined " + n
            + ( (isPrime) ? " is PRIME." : " is NOT PRIME." ) );
        }
        /**
        *   Improved O( n^(1/2)) ) Algorithm
        *    Checks if n is divisible by 2 or any odd number from 3 to sqrt(n).
        *    The only way to improve on this is to check if n is divisible by 
        *   all KNOWN PRIMES from 2 to sqrt(n).
        *
        *   @param n An integer to be checked for primality.
        *   @return true if n is prime, false if n is not prime.
        **/
        public static boolean primeBest(int n){
            int count = 0;
            // check lower boundaries on primality
            if( n == 2 ){ 
                printStats(++count, n, true);
                return true;
            } // 1 is not prime, even numbers > 2 are not prime
            else if( n == 1 || (n & 1) == 0){
                printStats(++count, n, false);
                return false;
            }
    
            double sqrtN = Math.sqrt(n);
            // Check for primality using odd numbers from 3 to sqrt(n)
            for(int i = 3; i <= sqrtN; i += 2){
                count++;
                // n is not prime if it is evenly divisible by some 'i' in this range
                if( n % i == 0 ){ 
                    printStats(++count, n, false);
                    return false;
                }
            }
            // n is prime
            printStats(++count, n, true);
            return true;
        }
    
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while(scan.hasNext()) {
                int n = scan.nextInt();
                primeBest(n);
                System.out.println();
            }
            scan.close();
        }
    }
    

    当输入质数2147483647时,它会产生以下输出:

    进行了23170次检查,确定2147483647为质数。

        14
  •  0
  •   John Kennedy Mendoza Aquino    6 年前

    在Intel Atom@1.60GHz、2GB RAM、32位操作系统中测试

    测试结果:
    长以下最大素数。最大值=9223372036854775807为9223372036854775783
    运行时间为171499毫秒或2分51秒

    public class PrimalityTest
    {
        public static void main(String[] args)
        {
            long current_local_time = System.currentTimeMillis();
            long long_number = 9223372036854775783L;
            long long_a;
            long long_b;
            if (long_number < 2)
            {
                System.out.println(long_number + " is not a prime number");
            }
            else if (long_number < 4)
            {
                System.out.println(long_number + " is a prime number");
            }
            else if (long_number % 2 == 0)
            {
                System.out.println(long_number + " is not a prime number and is divisible by 2");
            }
            else
            {
                long_a = (long) (Math.ceil(Math.sqrt(long_number)));
                terminate_loop:
                {
                    for (long_b = 3; long_b <= long_a; long_b += 2)
                    {
                        if (long_number % long_b == 0)
                        {
                            System.out.println(long_number + " is not a prime number and is divisible by " + long_b);
                            break terminate_loop;
                        }
                    }
                    System.out.println(long_number + " is a prime number");
                }
            }
            System.out.println("elapsed time: " + (System.currentTimeMillis() - current_local_time) + " millisecond/s");
        }
    }