欢乐赛#40 | T4题解

T4:

这道题要求我们求出第n个质数^[1]。

我们只要从2开始逐个判断每个数是否为质数，就可以找到第n个质数。

C++代码：

#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n){
    if(n == 1) return false;
    for(int i = 2;i < n;i++){
        if(n % i == 0) return false;
    }
    return true;
}
int main(){
    int n;
    cin >> n;
    int i = 0;
    int p[100010];
    int cnt = 0;
    
    while(cnt < n){
        i++;
        if(is_prime(i)){
            p[cnt] = i;
            cnt++;
        }
    }
    
    cout << p[n - 1];
    return 0;
}

Python 代码：

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,n):
        if n % i == 0:
            return False
    return True
n = int(input())
i = 0
p = []
while len(p) < n:
    i += 1
    if is_prime(i):
        p.append(i)
print(p[n-1])

---

1. 质数是指只能被1和自己整除的自然数。 ↩︎