資訊學奧賽一本通 1099：第n小的質數 | OpenJudge NOI 1.5 44

【題目連結】

ybt 1099：第n小的質數

OpenJudge NOI 1.5 44:第n小的質數

【題目考點】

1. 質數

• 質數的因數隻有1和它本身。

• 判斷數a是否是質數：循環變量i從2開始循環到 a \sqrt{a} a

  ​，若存在a能整除的數字（即a的因數），那麼a不是質數。否則a是質數。

bool isPrime(int a)//判斷a是否是質數，已知a >= 2
{
    for(int i = 2; i <= sqrt(a); i++)
    {
        if(a % i == 0)
            return false;
    }
    return true;
}
           

【解題思路】

• 設判斷質數的函數
• 設變量ct用于計數，每找到一個質數，ct就增加1，當ct等于n時，輸出剛剛找到的質數，就是第n小的質數。

【題解代碼】

解法1：

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int a)//判斷a是否是質數，已知a >= 2
{
    for(int i = 2; i <= sqrt(a); i++)
    {
        if(a % i == 0)
            return false;
    }
    return true;
}
int main()
{
    int n, ct = 0;//ct：計數 
    cin>>n;
    for(int i = 2; true; ++i) 
    {
        if(isPrime(i))//判斷i是否是質數 
        {
            ct++;
            if(ct >= n)//如果已經找到第n小的質數 
            {
                cout<<i;//那麼輸出i 
                return 0;
            }
        }
    }
}