检测素数的方法——O(logN)

理论上能快速检测出绝大部分数，除了Carmichaels数。

function expmod(a,exp,m){
        if(0 == exp) return 1;
        if(exp % 2){
            return a * (expmod(a, exp-1,m) % m) % m;
        }else{
            return Math.pow(expmod(a, exp / 2, m) % m, 2) % m;
        }
    }

    function test(n){
        if(n < 2 || n > 2 && !(n % 2)) return false;

        for(var i = 0; i < 20 && i < n-1; i++){
            var a = ((n - 1) * Math.random() | 0) + 1;
            if(expmod(a,n,n) != a) return false;
        }
        return true;
    }

用erlang实现的话：

test(N) ->
            test_more(20, N, N > 1).

    test_more(_,_,false) ->
            false;
    test_more(0,_,F) ->
            F;
    test_more(C,N,true) ->
            A = random:uniform(N - 1),
            test_more(C - 1, N, xmath:pow(A, N) rem N =:= A).

其中xmath:pow是自己写的大整数乘方算法（也是O(logN)复杂度）