Prime number（质数）

精典例题NOI-1.5-44:第n小的质数

描述

输入一个正整数n，求第n小的质数。

输入

一个不超过10000的正整数n。

输出

第n小的质数。

样例输入

10

样例输出

29

案例分析1

#include<iostream>

int main(){
    //freopen("1.533.in", "r", stdin);
    unsigned int n, m=0, i, j,sum=0;
    scanf("%d",&n);
    for(i=2; ;i++){
        for(j=2; j<=(i/j+1); j++){
            if( i%j==0 && j!=i ){
                m++;
                break;
            }
        }
        if(m==0) sum++;
        m=0;
        if(sum==n) break;
    }
    printf("%d", i);
    return 0;
}

安全案例2

#include <iostream>
#include <cmath>
#define MAXN 1000000

int main() {
    //freopen("1.533.in", "r", stdin);
    bool number[MAXN+1];
    for(int i=0; i<=MAXN; i++) number[i] = true;//先把所有数赋值为ture;

    int m = (int)sqrt(MAXN);//确认轮循的最大值是MANX开方；
    for(int i=2; i<=m; i++) //在此轮循内，给所有因数标false
        if(number[i])
            for(int j=2*i; j<=MAXN; j+=i) number[j] = false;

    int n, count=0;
    scanf("%d", &n);
    for(int i=2; i<=MAXN; i++)
        if(number[i] && ++count==n) {//++count 表示当number[i]为true时，先++count;类似i++, 属于后+1， 这个是用之前先加+ 
            printf("%d\n", i);
            break;
        }
    return 0;
}