大学学习java ,实践一个程序,要求运行出小于100的素数。
程序编写正确,cmd命令打开正确,但是最后没有出来 小于100的素数具体有哪些,只有一句话"小于100的素数有"后面却没有数字

解决方案 »

  1.   

    质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。例如2,3,5,7,11
      

  2.   

    Miller-Rabin 素性测试算法实现如下,供为参考
    public class PrimeTest {    public static void main(String[] args) {        for ( int i = 2 ; i < 100 ; i++ ) {
                if ( !MillerRabin.isComposite( i ) ) {
                    System.out.println( i );
                }
            }
        }    public static class MillerRabin {        public static boolean isComposite(int n) {
                if (n < 2) {
                    throw new IllegalArgumentException("number must greater than or equals 2");
                }            if (n == 2 || n == 3 || n == 5 || n == 7) {
                    return false;
                }            if ((n & 1) == 0) {
                    return true;
                }            if (n % 3 == 0) {
                    return true;
                }
                if (n % 5 == 0) {
                    return true;
                }
                if (n % 7 == 0) {
                    return true;
                }            int s = 0, d = n - 1;
                while ((d & 1) == 0) {
                    d >>= 1;
                    s++;
                }            if (n < 1373653) {
                    if (loopMillerRabin(s, d, n, 2, 3)) {
                        return true;
                    }
                } else if (n < 9080191) {
                    if (loopMillerRabin(s, d, n, 31, 73)) {
                        return true;
                    }
                } else {
                    // 4,759,123,141 已经超过 int 的最大值,因此大于等于 9080191 就采用 4,759,123,141 的基准测试
                    if (loopMillerRabin(s, d, n, 2, 7, 61)) {
                        return true;
                    }
                }
                return false;
            }        private static boolean loopMillerRabin(int s, int d, int n, int... t) {
                for (int i = 0; i < t.length; i++) {
                    if (testMillerRabin(t[i], s, d, n)) {
                        return true;
                    }
                }
                return false;
            }        private static boolean testMillerRabin(int a, int s, int d, int n) {
                if (montgomery(a, d, n) != 1) {
                    int e = 1;
                    for (int i = 0; i < s; i++) {
                        if (montgomery(a, d * e, n) + 1 == n) {
                            return false;
                        }
                        e <<= 1;
                    }
                    return true;
                }
                return false;
            }        private static int montgomery(int base, int exp, int mod) {
                if (base > 46340 || mod > 46340) {
                    long temp = 1;
                    long prod = base % mod;
                    while (exp > 1) {
                        if ((exp & 1) != 0) {
                            temp = (temp * prod) % mod;
                        }
                        prod = (prod * prod) % mod;
                        exp >>= 1;
                    }
                    return (int) ((temp * prod) % mod);
                } else {
                    int temp = 1;
                    int prod = base % mod;
                    while (exp > 1) {
                        if ((exp & 1) != 0) {
                            temp = (temp * prod) % mod;
                        }
                        prod = (prod * prod) % mod;
                        exp >>= 1;
                    }
                    return (temp * prod) % mod;
                }
            }
        }
    }