java基础算法----输出0到X之间的质数

质数定义：能且仅能被1和它本身整除的整数，称为质数，最小的质数是2。

思路：如果X在（2，X-1]这个区间内没有约数，则证明X是质数。

实现方法一：

/**
 * @author 蜗牛君
 * @create 2019-09-12 16:52
 */
/*输出100000之内的质数
* 质数的定义：能且只被1和它本身整除的数称为质数
* */
public class primeNumberTest {
    public static void main(String[] args) {
        //定义一个变量记录质数的个数
        int primeNumberCount = 0;
        //获取当前时间
        long start = System.currentTimeMillis();
        //计算0到100000之间质数的个数
        int num = 100000;
        for (int i = 2; i <= num; i++) {
            //定义一个bool型变量，用来判断是不是质数
            boolean isFlag = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    //如果在(2,i-1]这个区间内有约数，说明不是质数
                    isFlag = false;
                }
            }
            if (isFlag == true) {
                //System.out.println(i + "是质数");
                primeNumberCount++;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("本次运算用时：" + (end - start ) + "毫秒");
        System.out.println("0到"+ num + "之间共有"+ primeNumberCount +"个质数！");
    }
}

实现方法二：

是对方法一的优化，一旦判断X为质数，就通过countinue来跳出本次循环，节省算力，缩减计算时间

注：对循环体添加标签，可以方便break、continue直接跳转到指定的循环体

public class primeNumberTest {
    public static void main(String[] args) {
        int primeNumberCount = 0;
        //获取当前时间
        long start = System.currentTimeMillis();
        int num = 100000;
        lable:for ( int i = 2 ; i <= num ; i++ ){
            int count = 0;
            for (int j = 2; j < i;j ++){
                if (i % j == 0) {
                    //当在这个区间有公约数时，可判断不是质数，直接退出循环，不再进行后面的判断，可缩减部分运算时间
                    continue lable ;
                }
            }
            primeNumberCount++;
        }
        long end = System.currentTimeMillis();
        System.out.println("本次运算用时：" + (end - start ) + "毫秒");
        System.out.println("0到"+ num + "之间共有"+ primeNumberCount +"个质数！");
    }
}

 实现方法三：

再次优化，重点在二层循环时，减少了对 j 的判断的范围。

说明：如果 C = A x A，则只需要确定 C 在  ( 2 , A ] 的区间内没有约数，就可以证明 C 是质数。

public class primeNumberTest {
    public static void main(String[] args) {
        //定义一个变量来统计共有多少个质数
        int primeNumberCount = 0;
        //System.currentTimeMillis()用于获取当前时间
        long start = System.currentTimeMillis();
        //输出0到100000之间的所有质数
        int num = 100000;
        //对外层for循环添加一个标签，break或者continue可以根据标签跳到指定循环体
        lable:for ( int i = 2 ; i <= num ; i++ ){
            //Math.sqrt(i)用来求i的平方，类型为int
            for (int j = 2; j <= Math.sqrt(i);j ++){
                //如果i能被（2，Math.sqrt(i)]这个区间的数整除，说明不是质数，用continue直接    跳转到外层循环
                if (i % j == 0) {
                    continue lable;
                }
            }
            //System.out.println(i + "是质数");
            primeNumberCount++;
        }

        long end = System.currentTimeMillis();
        System.out.println("本次运算用时：" + (end - start ) + "毫秒");
        System.out.println("0到"+ num + "之间共有"+ primeNumberCount +"个质数！");
    }
}