算法笔记 - 素数问题

 

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

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]