一、判断当前数是否为素数

1.1 问题描述

输入一个整数，判断当前数是否为素数。

1.2 算法思路

一个数的因子是关于该数的平方根对称的，故只需要循环判断到该数的平方根为止。

1.3 代码实现

C++代码实现如下

bool isPrime(int num)
{
    if(num <= 1) return false;
    int sq = sqrt(num);
    for(int i = 2; i <= sq; i++)
    {
        if(num%i == 0) return false;
    }
    return true;
}

二、输出小于n的所有素数

埃拉托斯特尼筛法，简称埃氏筛，也称素数筛。这是一种简单且历史悠久的筛法，用来找出一定范围内所有的素数。

2.1 问题描述

输入一个整数，输出小于n的所有素数。

2.2 算法思路

1. 首先将2到n范围内的整数全写下来；
2. 其中2是最小的素数，将表中所有的2的倍数划去；
3. 表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去； ……
4. 以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去；
5. 反复操作直到m大于sqrt(n)，就获得一个小于n的素数数组。

2.3 代码实现

python3代码实现如下

isPrime = { x:True for x in range(2, n + 1)}
for key,value in isPrime.items():
    if key > cmath.sqrt(n):
        break
    if value:
        for i in range(2*key, n + 1, key):
            isPrime[i] = False
prime = [key for key,value in isPrime.items() if value]