試題 D: 質(zhì)數(shù) 本題總分：10 分
? ? ? ?【問題描述】 我們知道第一個(gè)質(zhì)數(shù)是 2拜马、第二個(gè)質(zhì)數(shù)是 3、第三個(gè)質(zhì)數(shù)是 5……請你計(jì)算 第 2019 個(gè)質(zhì)數(shù)是多少？
答案:17569
? ? ? ?題解：質(zhì)數(shù)，即大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的自然數(shù)坟漱。所以我們可以直接用兩個(gè)循環(huán)進(jìn)行嵌套，外層while循環(huán)用來計(jì)數(shù)更哄，里層用來判斷是否質(zhì)數(shù)芋齿。
解法一
? ? ? ?由于此題是填空題，不需要考慮到時(shí)間復(fù)雜度和空間復(fù)雜度成翩，我們可以直接用for循環(huán)嵌套

public static void main(String[] args) {
        //因?yàn)?是一個(gè)比較特殊的質(zhì)數(shù)所以循環(huán)從3開始,此時(shí)count=1
        int count = 1;
        for (int i = 3;; i++) {
            boolean flag=true;
            for (int j = 2; j < i; j++) {
                //如果i可以被除1和自身外的數(shù)整除,則跳出循環(huán)
                if (i%j==0) {
                    flag=false;
                    break;
                }               
            }
            //如果沒有找到可以整除i的數(shù),則此數(shù)為質(zhì)數(shù)
            if (flag==true) {
                count++;
            }
            if (count==2019) {
                System.out.println(i);
                break;
            }
        }
    }

解法二
? ? ? ?質(zhì)數(shù)除了題解中的特點(diǎn)外觅捆，還有一個(gè)特點(diǎn)：所有質(zhì)數(shù)都是在6n+1或者6n-1(n>0；n∈Z)麻敌，其次
如果一個(gè)數(shù)（>2）栅炒，對這個(gè)數(shù)求平方根，如果這個(gè)數(shù)能被這個(gè)數(shù)的平方根到2之間的任何一個(gè)整除說明就不是質(zhì)數(shù)术羔，如果不能就說明是質(zhì)數(shù)赢赊。所以如果此題需要考慮到時(shí)間復(fù)雜度的話我們可以簡化過程如下：

public class test4 {
        //判斷整數(shù)是否是質(zhì)數(shù)
    public static boolean IsPrime(int num) {
                //大于1小于等于3的整數(shù)都是質(zhì)數(shù)
        if (num <= 3) {
            return num > 1;
        }
               // 不在6的倍數(shù)兩側(cè)的一定不是質(zhì)數(shù)
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
                //開平方
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;

    }

    public static void main(String[] args) {
        int count = 0;
        for (int i = 0;; i++) {
            if (IsPrime(i)) {
                count++;
                if (count == 2019) {
                    System.out.println(i);
                    break;
                }
            }
        }

    }
}