判断一个大于2的正整数n是否为素数，请用至少两种方法实现

题目中给出的判断是否为素数的条件是大于2的整数n是否为正整数，所以我们需要用至少两种方法判断n是否为素数。

方法一：试除法

试除法指的是，对于一个大于2的整数n，将其与小于等于n的所有素数依此相除，如果都不能整除，则n是素数。这个方法的缺点是需要找到小于等于n的所有素数，而素数的判断又需要用到试除法，因此这个方法不是很实用。

方法二：费马小定理

费马小定理是指若p为素数，a是任意整数，则a^p-a能被p整除。可以根据费马小定理写出判断n是否为素数的代码：

def is_prime(n):
if n == 2:
return True
elif n < 2 or n % 2 == 0:
return False
else:
for i in range(3, int(n**0.5)+1, 2):
if n % i == 0:
return False
return True

参考资料：
1. https://zh.wikipedia.org/wiki/%E8%AF%95%E9%99%A4%E6%B3%95
2. https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86

相关问题

判断一个大于 2 的正整数 n 是否为素数，请用至少两种方法实现

方法一：试除法

试除法是判断一个数是否为素数的常用方法，其基本思想是从 2 到 sqrt(n) 的所有整数都试图去除 n，如果都无法整除，则 n 是素数。

Python 代码实现如下：

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

方法二：埃氏筛法

埃氏筛法是一种筛选法，其基本思想是先把从 2 开始的所有整数写下来，然后从 2 开始，将每个素数的倍数都标记成合数，直到筛完所有小于等于 n 的数，留下的未被标记的数就是素数。

Python 代码实现如下：

def is_prime(n):
    if n <= 1:
        return False
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(math.sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return is_prime[n]

以上两种方法分别是试除法和埃氏筛法，都可以实现判断一个大于 2 的正整数 n 是否为素数。

判断一个大于 2 的正整数 n 是否为素数，请用至少两种方法实现。

方法一：试除法

试除法是素数判断的一种基本方法，即用 2 到 sqrt(n) 之间的所有正整数去除 n，若都无法整除，则 n 是素数，否则 n 不是素数。

代码实现：

import math

def is_prime(n):
    if n <= 1: # 1 不是素数
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

方法二：埃氏筛法

埃氏筛法是一种更高效的素数筛法，其基本思想是从 2 开始，将每个素数的倍数都标记成合数，直到筛完所有小于等于 n 的素数。

代码实现：

def is_prime(n):
    if n <= 1: # 1 不是素数
        return False
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(math.sqrt(n))+1):
        if is_prime[i]:
            # 将 i 的倍数标记为合数
            j = i * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime[n]

以上两种方法都可以判断一个大于 2 的正整数是否为素数。