题目类型: 素数个数统计

题目要求: 统计n以内的素数个数

public class PrimeNumber1 {public static void main(String[] args) {//打印100以内的素数个数(预计结果为25)System.out.println("暴力算法统计素数个数为"+bf(100));//测试结果确实为25}/*** 使用暴力算法统计素数个数* @param n 统计素数边界值* @return 返回int型的素数个数*/public static int bf(int n) {//统计素数个数的计数器int count = 0;//外层for循环遍历(其时间复杂度为n)for (int i = 2; i < n; i++) {//使用三元运算符: 判断数字i是否为素数, 若是素数(值为false), count值加1, 否则保持不变
//            count += isPrime(i) ? 1 : 0;//算法改进后进行素数判断count += isPrime2(i) ? 1 : 0;}return count;}/*** 判断当前数字是否为素数 原版* @param x 整型自然数* @return 布尔型值true或者false*/private static boolean isPrime(int x) {//内层for循环遍历(其时间复杂度为x)for (int i = 2; i < x; i++) {//判断x是否为素数(即判断x是否能够被i整除)if(x % i == 0) {//若能被整除, 则返回falsereturn false;}}//若不能被整除, 则返回truereturn true;}/*** 判断当前数字是否为素数 改进版* 在第一版基础上降低算法时间复杂度* @param x 整型数字* @return 布尔型值true或者false*/private static boolean isPrime2(int x) {/*** 问题: 使用暴力算法时, 总的时间复杂度为n+x, 执行效率太低* 改进思路:* i的取值范围其实没必要取到x, 实际上只需要取到根号下x即可;** 为什么取到根号下x就可以了呢？* 假设x值为12, 那么12能被整除的组合因子有哪些呢？* 包括: 1*12 2*6 3*4 4*3 6*2 12*1* 我们发现, 前面三个跟后面三个的关系只是两个因子位置颠倒,* 也就是满足乘法交换律, 只要能被前三个组合中的两个因子整除,* 也一定能被后三个组合中的两个因子整除, 因此取到根号下x即可;* 这样不仅可以减少for循环次数, 而且时间复杂度也随之降低*///内层for循环遍历
//        for (int i = 2; i < x; i++) {//方式一: 使用Math.sqrt()函数开根号for (int i = 2; i <= Math.sqrt(x); i++) {//方式二: 使用i * i < x表示(作用相当于x开根号)
//          for (int i = 2; i * i <= x; i++) {//判断x是否为素数(即判断x是否能够被i整除)if(x % i == 0) {//若能被整除, 则返回falsereturn false;}}//若不能被整除, 则返回truereturn true;}}