Problem Description.png

從鍵盤(pán)輸入得到n，輸出第n個(gè)素?cái)?shù)。
2是最小的素?cái)?shù)（常識(shí)嘛嘻嘻）。題目描述中的k<=10000基本不需要額外的代碼操作，可通過(guò)OJ。

/*
 * 輸出第k個(gè)素?cái)?shù),比如輸入3,輸出5;輸入7,輸出17
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PrimeNumber {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            // 輸出第n個(gè)素?cái)?shù)
            int n = scan.nextInt();
            int current = 2;//最小的素?cái)?shù)是2
            int sum = 0;
            List<Integer> list = new ArrayList<>();//list來(lái)保存前n個(gè)素?cái)?shù)
            for (;;) {
                //除了2以外的所有偶數(shù)都不是素?cái)?shù)，為了減少判斷將這些偶數(shù)避開(kāi)
                if (current > 2 && current % 2 == 0) {//如果current為大于2的偶數(shù)
                    current++;//current++得到奇數(shù),利用continue進(jìn)行下一次循環(huán)
                    continue;
                }
                int a = -1;
                //下面i的循環(huán)條件值得玩味,優(yōu)化下得到更少的判斷次數(shù)更好的性能更小的時(shí)間復(fù)雜度
                for (int i = 2; i <= Math.sqrt(current); i++) {
                    if (current % i == 0) {
                        a = 0;
                        break;
                    }
                }
                //a==-1,則當(dāng)前current是素?cái)?shù),sum用于控制得到n個(gè)素?cái)?shù)
                if (a == -1) {
                    sum++;
                    // System.out.println(current);
                    list.add(current);

                }
                if (sum == n) {
                    break;
                }
                current++;
            }
            //輸出list的最后一個(gè)數(shù)(即第n個(gè)素?cái)?shù))
            System.out.println(list.get(list.size() - 1));
        }
    }
}