统计n以内的素数个数
素数：素数又叫质数,素数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。（prime number）
方法一：暴力算法
/**
* 暴力算法解决：素数个数统计
*/
public class PrimeNumber1 {
public static void main(String[] args) {
int num = bf(100);
System.out.println(num);
}
/**
* 使用暴力算法解决元素个数
* @param n 统计素数边界值
* @return 返回一共有多少个元素
*/
public static int bf(int n) {
//统计元素个数的计数器
int count = 0;
//外层for循环遍历(判断元素是否为素数)
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 返回bool类型，是素数计数器加一，不是素数计数器加0；
*/
private static boolean isPrime(int x){
//内层for循环遍历(其时间复杂度为x)
for (int i = 2; i < x; i++) {
//判断x是否为素数（是否能被i给整除）
if (x % i == 0){
//若能被整除, 则返回false
return false;
}
}
//若不能被整除, 则返回true
return 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) {
//若能被整除, 则返回false
return false;
}
}
//若不能被整除, 则返回true
return true;
}
}
方法二：
核心: 区分素数(质数)和非素数(合数), 并将它们分别做上标记
- 怎么样区分质数和合数？
如果要统计100以内的素数，例如数字12，12的有一个组合因子为 2 * 6，由于2和3都是素数(只能被1和它自身整除)，而它们的乘积为6 (2*3)，那么6就是一个非素数(即合数)；
对于这些合数，我们可以通过对它进行标记，然后不对其进行遍历，这样就可以大大减少遍历次数;
- 怎么对这些合数进行标记呢？
可以使用倍增的方式, 例如2的倍数: 22=4, 23=6, 24=8, 25=10, 2*6=12 (这些乘积要小于n)；
而4,6,8,10,12这些数都是合数, 合数4的因子是两个2, 所以当3遍历完后, 轮到4了, 就可以直接跳过4
package com.kuang.leetcode2;
/**
* @ClassName PrimeNumber2
* @Description 素数个数统计-使用埃氏筛选法处理
* @Author 狂奔の蜗牛rz
* @Date 2021/8/19
*/
public class PrimeNumber2 {
public static void main(String[] args) {
System.out.println("埃氏筛选法统计素数个数为: "+eratosthenes(100));
}
/**
* 埃氏筛选法 原版
* 区分素数和合数, 并进行标记, 统计素数个数
* @param n 整型数字
* @return 素数的个数
*/
public static int eratosthenes(int n) {
//给每个数字设置一个布尔值类型的标记位(默认值为false)
/**
* 先假设所有数字都为素数, 即标志位为默认值false;
* 若当前数字为合数, 则将标志位修改为true
*/
boolean[] isPrime = new boolean[n];
//计数器(统计素数个数)
int count = 0;
//外层for循环(0和1不是素数, 所以i的初值为2)
for (int i = 2; i < n; i++) {
//判断当前数字是否为素数(即标志位是否为false)
if(!isPrime[i]) {
//若当前数字为素数(即标志位为false), 则计数器加1
count++;
//内层for循环(变量j是合数的标记位, 先将j的初值设为0, 步长设为1)
//for (int j = 0; j < n ; j++ ) {
/**
* 那么j的初值应该设为多少呢？
* 首先需要找出合数, 其中一个因子为2, 另一个因子为i, 所以j的初值为2*i
* 那么自增的步长又该如何设置？
* 内循环中j初值为2*i, 那么下一轮内循环的j值理应为3*i, 而下下轮内循环j值为4*i,
* 其实就是系数发生了递增, 我们只需在每轮内循环结束后, 将j值加i,
* 这样下轮内循环的j值就为2*i+i(即3*i), 实现了系数递增效果,
* 因此步长为每次加i, 即j+=i
*/
for (int j = 2 * i; j < n ; j+=i ) {
//若当前数字为合数, 则将标志位修改为true
isPrime[j] = true;
}
/**
* 先执行了count++操作, 然后进行素数判断, 是否会出现素数个数多加？
* 不会, 因为首轮外循环时, 第一个数为2, 本身就是素数,
* 当进行首次素数判断时, 计数器count的值会自增加1,
* 然后开始执行内循环, 将后面出现的合数的标记位修改为true
*/
}
}
//最后将素数个数进行返回
return count;
}
/**
* 埃氏筛选法 改进版
* 在原版基础上, 进行了算法优化, 降低了时间复杂度
* @param n 整型数字
* @return 素数的个数
*/
public static int eratosthenes2(int n) {
//给每个数字设置一个布尔值类型的标记位(默认值为false)
/**
* 先假设所有数字都为素数, 即标志位为默认值false;
* 若当前数字为合数, 则将标志位修改为true
*/
boolean[] isPrime = new boolean[n];
//计数器(统计素数个数)
int count = 0;
//外层for循环(0和1不是素数, 所以i的初值为2)
for (int i = 2; i < n; i++) {
//判断当前数字是否为素数(即标志位是否为false)
if(!isPrime[i]) {
//若当前数字为素数(即标志位为false), 则计数器加1
count++;
//内层for循环
// for (int j = 2 * i; j < n ; j+=i ) {
/**
* 埃氏筛选法怎样进行优化呢？
* 当外循环中i=2时, 内循环中的j值分别为
* 2*2, 3*2, 4*2, 5*2 ...
* 当i值为3时, j值分别为:
* 2*3, 3*3, 4*3, 5*3, 6*3 ...
* 当i值为4时, j值分别为:
* 2*4, 3*4, 4*4, 5*4, 6*4 ...
* 仔细观察后发现:
* i=2中的3*2在i=3中再次出现, 4*2在i=4中再次出, i=3中的4*3在i=4中再次出现,
* 也就是说我们在i=3中只要计算3*3之后的, 在i=4中只需要计算4*4之后的,
* 因此j的初值设置为i*i即可
*/
for (int j = i * i; j < n ; j+=i ) {
//若当前数字为合数, 则将标志位修改为true
isPrime[j] = true;
}
}
}
//最后将素数个数进行返回
return count;
}
}
