如何找到一个给定整数最近的质数？

Question

除了暴力的试除法以外，还有什么方法吗，这里应该不能用筛除，那就得一个一个试啦？

Answer 1

我的数学不好，但我擅长搜索，谷大仙的第一条就是一个非常靠谱的讨论串

http://math.stackexchange.com/questions/35300/what-is-the-most-efficient-algorithm-to-find-the-closest-prime-less-than-a-given

先用快速判断可能性的算法可以高速筛掉多数，然后再用精准的算法最终确定

用费马小定理判断伪质数（简单，容易理解）

http://primes.utm.edu/prove/prove2_2.html

Miller–Rabin判断伪质数（实际被运用）
http://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C

AKS质数判定（确定性算法）
http://zh.wikipedia.org/wiki/AKS%E8%B3%AA%E6%95%B8%E6%B8%AC%E8%A9%A6

Answer 2

没有想到更好的方法，写一个 PHP 版的试除法，希望有人能提供更优的算法。:)

function isPrime($n) 
{
    if($n < 2) return false;

    $m = sqrt($n);
    for($i = 2;$i < $m;$i ++) {
        if($n % $i == 0) return false;
    }

    return $n;
}

function closestPrime($n)
{
    if(isPrime($n)) {
        echo 'You enter a prime.';
        return false;
    }

    $left = $right = $n;

    while(!isPrime(-- $left));
    while(!isPrime(++ $right));

    $result = ($n - $left) > ($right - $n) ? $right : $left;
    echo 'The closet prime of '.$n.' is '.$result;
}