第十届蓝桥杯C组——试题 D: 质数

试题 D: 质数 本题总分：10 分
       【问题描述】 我们知道第一个质数是 2、第二个质数是 3、第三个质数是 5……请你计算 第 2019 个质数是多少？
答案:17569
       题解：质数，即大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。所以我们可以直接用两个循环进行嵌套，外层while循环用来计数，里层用来判断是否质数。
解法一
       由于此题是填空题，不需要考虑到时间复杂度和空间复杂度，我们可以直接用for循环嵌套

public static void main(String[] args) {
        //因为2是一个比较特殊的质数所以循环从3开始,此时count=1
        int count = 1;
        for (int i = 3;; i++) {
            boolean flag=true;
            for (int j = 2; j < i; j++) {
                //如果i可以被除1和自身外的数整除,则跳出循环
                if (i%j==0) {
                    flag=false;
                    break;
                }               
            }
            //如果没有找到可以整除i的数,则此数为质数
            if (flag==true) {
                count++;
            }
            if (count==2019) {
                System.out.println(i);
                break;
            }
        }
    }

解法二
       质数除了题解中的特点外，还有一个特点：所有质数都是在6n+1或者6n-1(n>0；n∈Z)，其次
如果一个数（>2），对这个数求平方根，如果这个数能被这个数的平方根到2之间的任何一个整除说明就不是质数，如果不能就说明是质数。所以如果此题需要考虑到时间复杂度的话我们可以简化过程如下：

public class test4 {
        //判断整数是否是质数
    public static boolean IsPrime(int num) {
                //大于1小于等于3的整数都是质数
        if (num <= 3) {
            return num > 1;
        }
               // 不在6的倍数两侧的一定不是质数
        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;
                }
            }
        }

    }
}