筛选法求质数

筛选法求质数（求小于等于N的所有素数）

一般的思路：对2~N的每一个数循环判断是否是素数，时间复杂度为N的3/2次方
算法思路： （筛选法）依次筛去2~N中小于等于根号N的数的倍数

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <ctime>
#define N 100000
using namespace std;


int main()
{
    clock_t startTime,endTime; //记录程序运行时间
    int prim[N+1];
    int num=0,coun=2;
    startTime = clock();
    for(int i=0;i<=N;i++)
    {
        prim[i] = 1;  //记录数是否被筛去，为1，则未被筛出
    }
    for(int i=2;i*i<=N;i++)
    {
        if(prim[i] == 1)  //若此数未被筛出
        {
            for(int j=i*2;j<=N;j=i*coun)//自己不能筛出自己,只能筛选自己的倍数
            {
                if(j % i == 0)
                    prim[j] = 0;
                coun++;
            }
            coun=2;
        }
    }
    endTime = clock();
    cout<<(double)(endTime-startTime)<<endl;
    for(int i=2;i<=N;i++)
    {
        if(prim[i] == 1)
        {
            cout<<i<<" ";
            num++;
        }
        if(num == 10)
            {
                cout<<endl;
                num=0;
            }
    }
    return 0;
}

本博客持续更新中，若有不懂的或不正确的欢迎留言