public static boolean isPrime(int n){
    if (n <= 3) {
        return n > 1;
    }
    for(int i = 2; i < n; i++){
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static boolean isPrime(int num) {
    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;
}

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // Scanner in = new Scanner(System.in);
        // int n = in.nextInt();
        // in.close();
        Stack<Integer> a = new Stack<>(), b = new Stack<>();
        int n = 100000;
        long s = System.currentTimeMillis(), e;
        for (int i = 1; i < n; i++) {
            if (f(i))
                a.push(i);
        }
        e = System.currentTimeMillis();
        System.out.println(e - s + " ms");
        s = System.currentTimeMillis();
        for (int i = 1; i < n; i++) {
            if (func(i))
                b.push(i);
        }
        e = System.currentTimeMillis();
        System.out.println(e - s + " ms");
        System.gc();
    }

    static boolean f(int n) {
        if (n <= 3)
            return n > 1;
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    static boolean func(int n) {
        if (n <= 3)
            return n > 1;
        if (n % 6 != 1 && n % 6 != 5) {
            return false;
        }
        int tem = (int) Math.sqrt(n);
        for (int i = 5; i <= tem; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }
}