1106 质数检测

题目

解题思路

1.直接暴力
2.打表

代码

/* 方法一：打表，虽然思路是对的，但此题不行，应为 数据可能为1e9，数组开太大，会爆 */
#include<iostream>
#include<math.h>
#include<string>
using namespace std;
const int maxnu = 1e9+5;
const int maxn = 1005;
int n ;
int a[maxn];
bool vis[maxnu];
void init()
{
    memset(vis,0,sizeof(vis));
}
int main()
{
    init();
    cin >> n;
    int maxnum;
    for(int i=0; i<n; ++i)
    {
        cin >> a[i];
        maxnum = max(maxnum,a[i]);
    }
    for(int i=2; i<=(int)sqrt(maxnum); ++i)
    {
        if(!vis[i])
        {
            for(int j=i*i; j<=maxnum; j+=i)
                vis[j] = 1;
        }
    }
    for(int i=0; i<n; ++i)
    {
        if(vis[a[i]])
            cout << "No" <<endl;
        else
            cout << "yes" << endl;
    }

    return 0;
}

/* 方法二：暴力 */
#include<iostream>
#include<math.h>
using namespace std;
int n;
bool isPrime(int x)
{
    int k = (int)sqrt(x);
    bool flag = true;
    for(int i=2; i<=k; ++i)
    {
        if(x%i == 0)
        {
            flag = false;
            break;
        }
    }
    return flag;
}
int main()
{
    cin >> n;
    int num;
    for(int i=0; i<n; ++i)
    {
        cin >> num;
        if(isPrime(num))
            cout << "Yes" <<endl;
        else
            cout << "No" <<endl;
    }

    return 0;
}