HLJOJ1171(大素數判定)

HLJOJ1171(大素數判定)

多組測試數據，每組測試數據第一行輸入一個正整數n（0< n < 10^9）。

每組測試數據，若n為素數，那麼輸出“YES”，否則輸出“NO”。（引號不輸出）

思路：由於n非常的大，打表nlogn也不行，我們換一種思路，我們不打10^9，我們只打出它的開平方10^5就差不多了，找出小於10^5以內的素數，然後我們判定n的時候再用

普通素數判別法判定就行

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
const double eps = 1e-6;
const int INF = 10000000;
int n, m , k;
 
const int maxn = 60001;
 
bool ispri[maxn];
 
int pri[maxn];
 
void is()
{
    int cnt = 0;
    memset(ispri , true , sizeof(ispri));
    ispri[1] = 0;
    for(LL i  = 2 ; i < maxn ; i ++)
    {
        if(ispri[i])
        {
            pri[++ cnt] = i;
            for(LL j = i * 2 ; j < maxn ; j += i)
                ispri[j] = false;
        }
    }
}
 
bool isp(int n)
{
    int m = sqrt(n);
    for(int i = 1 ; pri[i] <= m ; i ++)
        if(n % pri[i] == 0)
            return false;
    return true;
}
 
int main()
{
 
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    is();
    while(~scanf("%d",&n))
    {
        if(n == 0 || n == 1)
        {
           printf("NO\n");
            continue;
        }
 
        if(isp(n))
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
 
    }
}