素数

零：素数

　　质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为素数（质数）；否则称为合数。

---

---

---

一：最基本的素数判定

　　先求开方,避免溢出. 开方注意四舍五入 floor(XX + 0.5)：

#include <iostream>
#include <cmath>

bool is_prime(int x)   //是否是素数
{
    if(x<=1)  return false;
    int mid=floor(sqrt(x)+0.5);   //找到中间的那个数,注意这里的四舍五入, 用到 floor(**+0.5)
    for (int i=2;i<=mid;i++)   //要是这里用 i*i<=x 的话可能溢出!!!
    {
        if (!(x%i))
        {
            return false;   //不是
        }
    }
    return true;
}

int main(void)
{
    for (int i=0;i<100;i++)
    {
        std::cout<<i<<"is prime: "<<is_prime(i)<<"\n";
    }
    std::cin.get();
    return 0;
}

---

---

---

二：筛选法与素数表

　　上面的方法是一个一个地判断，如果要判断从2到20000的这么多怎么提高效率？这里用筛选法，思想是：先预处理一个有N个数字的bool数组isPrime[N]，下标n对应的数组值表明整数n是不是一个素数。这样只要预处理一次，以后直接取即可。

　　如何预处理：从2开始依次遍历直到sqrt(N)，如果 isPrime[n] == true，则对于小于N的n的二三四五等整数倍的数m，isPrime[m] = false。其实这里就是把从2开始的数字的大于1的整数倍的数都设置成不是，是那些数倍数的数字肯定不是素数了嘛。

#include <iostream>
#include <cmath>

using std::sqrt;
using std::cout;
using std::cin;
using std::endl;

const int N = 160;
bool isPrime[N];

void setPrime(void)
{
    memset(isPrime, true, sizeof(isPrime));        //刚开始设置为都是素数
    int mid = floor(sqrt(double(N)) + 0.5);

    for (int i = 2; i <= mid; i++)
    {
        if(isPrime[i])        //注意这个判断！！！如果没有这个判断的话，也可以，但做了很多重复的计算
        {
            int miltiple = 2;
            while(i * miltiple < N)
            {
                isPrime[i * miltiple] = false;        //设置不是素数的
                miltiple++;
            }
        }    
    }
}

void show(void)
{
    for (int i = 2; i < N; i++)
    {
        cout << i;
        if(isPrime[i])
            cout << " is prime";
        else
            cout << " is not prime";
        cout<<endl;
    }
}

int main(void)
{
    setPrime();
    show();
    cin.get();
}

注意22行的while循环：

//初始化都是素数标志都是true，那么在后面的for循环中，如果遇到一个数A是false，
//那么A的false一定是因为数字A是前面某个数B的倍数，既然如此，对于数A来说，
//A的一二三四倍都是数B的某个倍数，也就是说已经被数B设置过了，所以A不需要再设置

---

---

---

三：节省空间

　　上面用bool数组太浪费了，bool也不是一个位，为了用一个bit表示是不是素数，我们用 bitset ,这样就节省了。

#include <iostream>
#include <cmath>
#include <bitset>

using std::sqrt;
using std::cout;
using std::cin;
using std::endl;
using std::bitset;

const int N = 160;
bitset<N> isPrime(true);


void setPrime(void)
{
    int mid = floor(sqrt(double(N)) + 0.5);

    for (int i = 2; i <= mid; i++)
    {
        if(isPrime[i])        //注意这个判断！！！如果没有这个判断的话，也可以，但做了很多重复的计算
        {
            int miltiple = 2;
            while(i * miltiple < N)
            {
                isPrime[i * miltiple] = false;        //设置不是素数的
                miltiple++;
            }
        }    
    }
}

void show(void)
{
    for (int i = 2; i < N; i++)
    {
        cout << i;
        if(isPrime[i])
            cout << " is prime";
        else
            cout << " is not prime";
        cout<<endl;
    }
}

int main(void)
{
    setPrime();
    show();
    cin.get();
}