程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HLJOJ1171(大素數判定)

HLJOJ1171(大素數判定)

編輯:關於C++

多組測試數據,每組測試數據第一行輸入一個正整數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");
        }
 
    }
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved