判断质数 Python Java C++

来自百度百科中的定义：

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

那么怎么使用程序去判断一个数，是否是质数。

初始版本：

最原始的判断方法就是用for循环遍历每一个数，这种方法固然可行，但是如果用来解题，恐怕解题速度不太理想。

升级版本：

细想一下，1*3和3*1是不是一回事，所以我们循环判断这个数是不是质数的时候，只需要循环到这个数的开方即可

import math
math.sqrt(n)

最终版本：

再观察一下，除了2和3，所有的质数都在6的倍数附近，要么是6-1，要么是6+1；

6 n ( + 0 ) 6n(+0) 6n(+0)：一定可以被3整除 6 n + 2 6n+2 6n+2：一定可以被2整除 6 n + 3 6n+3 6n+3：一定可以被3整除 6 n + 4 6n+4 6n+4：一定可以被2整除 只有 6 n + 1 6n+1 6n+1和 6 n + 5 6n+5 6n+5(即 6 n − 1 6n-1 6n−1)是不确定的。

所以在执行循环之前，可以先判断一下这个数是否是 6 n + 1 6n+1 6n+1或者 6 n − 1 6n-1 6n−1；即(n+1)%6和(n-1)%6是否等于0。

最终代码如下：

Python：

def isPrime(n):
    if n <= 3:
        return n >= 2
    else:
        if (n + 1) % 6 != 0 and (n - 1) % 6 != 0:
            return False
        for i in range(2, int(math.sqrt(n)) + 1):	# math.sqrt返回值是浮点型，所以要加一个int()
            if n % i == 0:
                return False
    return True

Java：

boolean isPrime(int n) {
          
   
        if (n <= 3)
            return n >= 2;
        if ((n + 1) % 6 != 0 && (n - 1) % 6 != 0)
            return false;
        for (int i = 2; i < (int) Math.sqrt(n) + 1; i++) {
          
   
            if (n % i == 0)
                return false;
        }
        return true;
    }

C/C++：

#include <cstdio>
#include <cmath>

bool isPrime(int n)
{
          
   
    if (n <= 3)
        return n >= 2;
    if ((n + 1) % 6 != 0 && (n - 1) % 6 != 0)
        return false;
    for (int i = 2; i < (int)sqrt(n) + 1, i++)
    {
          
   
        if (n % i == 0)
            return false;
    }
    return true;
}