素数对猜想

题目

“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N(<10⁵)，请计算不超过N的满足猜想的素数对的个数。

输入例子

20

输出例子

4

解题思路

这个比较简单，看题目，能确定一点，一个素数对，有两个相差 2 的素数组成。那么接下来就可以用 n除以2到根号n之中的任意一个数，如果能被整除，那么就不是素数，如果不能被整除，那么就是一个素数。如果发现了一个素数，那么就用这个素数相差2的数再去判断，如果还是素数，那么就有了一个素数对。

代码

/**
* 判断是不是一个素数
* @param {int} $num
*/
function isPrime($num)
{
    //如果 n < 2 那么它不是一个素数
    if ($num < 2) {
        return false;
    }

    //如果 n 能整除 2 到 根号n 之中的任意一个数 那么他就不是 素数
    //sqrt 函数 用来 开平方根
    for ($i = 2; $i <= intval(sqrt($num)); $i++) {
        if ($num % $i == 0) {
            return false;
        }
    }

    return true;

}

function test($num)
{
    $count = 0;
    for ($i = $num; $i >= 5; $i--) {
        //如果 n 和 n - 2 都是素数，那么就有一个素数对
        if ($this->isPrime($i) && $this->isPrime($i - 2)) {
            ++$count;
        }
    }
    printf($count);
}