1181 质数中的质数（质数筛法）

题目

解题思想

很简单一道题，质数打表

代码

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn = 1e6+5;
int vis[maxn];
int a[maxn];
void init()
{
    memset(vis,0,sizeof(vis));
}
bool isPrime(int x)
{
    bool flag = true;
    for(int i=2; i<=(int)sqrt(x); ++i)
    {
        if(x%i == 0)
        {
            flag = false;
            break;
        }
    }
    return flag;
}
int main()
{
    init();
    int n;
    cin >> n;
    //下面俩个for是质数打表
    for(int i=2; i<=(int)sqrt(maxn); ++i)
    {
        if(!vis[i])
          for(int j=i*i; j<=maxn; j+=i)
          {
              vis[j] = 1;
          }
    }
    int index = 1;
    //将打表好的质数装到数组中
    for(int i=2; i<=maxn; ++i)
        if(!vis[i])
           a[index++] = i;

    for(int i=1; i<=maxn; ++i)
        if(a[i] >= n)
         {
             if(isPrime(i))
             {
              cout << a[i] <<endl;
              break;
             }
         }
    return 0;
}