素数判决和素数序列生成

柔光的暖阳◎ 2022-06-11 01:21 311阅读 0赞

## 前言 ##

质数又称素数。一个大于1的自然数，除了**1和它自身**外，不能被其他自然数整除的数叫做质数。

## 1. 素数的判定 ##

方法1

bool IsSushu(const int num)
    {
        if(num < 2)
            return false;
    
        int temp(num);
        for(int i=2; i<temp; ++i)
        {
            if(temp%i == 0)
                return false;
        }
    
        return true;
    }

方法2

bool IsSushu_Sqrt(const int num)
    {
        if(num < 2)
            return false;
    
        int temp(num);
        int loop = (int)sqrt(temp);
        for(int i=2; i<=loop; ++i)
        {
            if(temp%i == 0)
                return false;
        }
    
        return true;
    }

这里使用num的平方根作为循环的上界，是因为每个整除num的整数a，都有一个整数b使得a\*b=num。如果a>loop，那么b<loop。因而当数字a大于loop时就不需要进行检查了，已经检查过了。

## 2. 素数序列生成 ##

这里使用埃拉托斯尼特筛选法，埃拉托斯尼特筛选法能够非常高效地生成素数的序列，原理是剔除所有可能被素数整除的非素数。

//求取当前素数的下一个素数
    int GetNextSushu(const int start, const int max_num, bool* flag)
    {
        int next(start+1);
        while(!flag[next] && next<=max_num)
            ++next;
    
        return next;
    }
    
    //给出小于max_num的全部素数
    std::vector<int> GetSushu(const int max_num)
    {
        std::vector<int> vec;
        if(max_num < 2)
            return vec;
    
        bool flag[max_num+1];
        for(int i=0; i<=max_num; ++i)
            flag[i] = true;
    
        //初始化
        flag[0] = false;
        flag[1] = false;
    
        int start = 2;  //素数的起始位置
        vec.push_back(start);
        while(start <= max_num)
        {
            //划掉当前素数的倍数，这些数字都不可能是素数了
            for(int i=(start*start); i<=max_num; i+=start)
            {
                flag[i] = false;
            }
    
            start = GetNextSushu(start, max_num, flag);
    
            if(start > max_num)
                break;
    
            vec.push_back(start);
        }
    
        return vec;
    }

生成100以内的素数

![SouthEast][]

[SouthEast]: /images/20220611/688011d0a91f40a7a6a6d163bd3f7f8f.png