质数表的生成以及质数的判断

最近看了一个问题，涉及到质数的判断。以前没有留意过这方面的方法。但是特意找了下资料发现自己解决这个问题的方法还是很笨的，网上有许多更好的方法。这里做个简单的总结。

生成质数表

首先最笨的办法是生成一个表来判断。以前上离散数学的时候讲过可以用筛法求这个表。把这个表先算出来显然是很划算的。但是，生成这个表也有好和不好的方法。

Eratosthenes筛法

给出要筛数值的范围\(\sqrt(n)\)，然后把范围内2的倍数划去，然后找到第一个没被划去的数。再把这个数的倍数划去，然后再找第一个没被划去的数，如此重复。。。

欧拉筛法

这个方法比上一个筛法要快很多。原因是上一个算法会重复筛某些数（尽管标记为已经筛除，但是还是要判断）。比如说6会被2和3筛去。这个方法主要思想就是每个合数只被最小的质因数筛掉。

void gen(){
    for(int i=2; i<=N; i++){
        if(!check[i]){//没被划去的i，是质数
            prime[total++]=i;
            isPrime[i] = true;
        }
        for(int j=0; j<total; j++){
            int t = i*prime[j];//i和之前所有的质数相乘
            if(t>N)break;
            check[t] = true;//筛掉
            if(i%prime[j]==0)break;
            //保证了每个合数只会被它的最小素因子筛掉
        }
    }//end enum
}

上面代码prime是保存质数的，而isPrime是一个标记数组。查表判断就靠isPrime了，N是范围。

只生成一部分质数表

上面的方法尽管高效但是浪费空间，而且要判断的数字比较大的时候，事先要准备一个比较大的表，计算起来也是比较费事的。折衷的方法是生成一部分表。表内的最大质数为可能检测的最大数的平方根。这样小于平方根的直接判断，大于平方根的可以从表头循环检查能否整除待检测的数。

拉宾-米勒测试

这种方法不用生成表。但是给出的结果不一定准确。多次测试的话，可以减小误判的概率。详细的介绍见链接