求质数的算法

title: 求质数（算法）date: 2020-12-10 22:44:41
tags: C++
categories: 算法

用矩阵表减少运行时间

#include <iostream>
#include <string.h>
#define N 1000000
using namespace std;
int s[N];  //s[i] = 0表示 i 是素数 
int main()
{
    int n,i,j,sum = 0;
    memset(s,0,sizeof(s));
    cin>>n;
    for(i = 2; i <= n; i++)
    {
        if(s[i] == 0)  //i为素数 
        {
            sum++;
            for(j= 2; j*i <= n;j++)
            {
                s[i*j] = 1;  //i为素数,则i*j为合数 
            }
        }
    }
    cout<<sum+1;
    return 0;
}