面试官手里那些秀你一脸的求质数大法

这些求质数的算法,都是小编一点一点看的大佬们的方法,自己积累的,如果有什么描述的不对的地方还望大佬赐教,多交流才能进步,加油,冲冲冲!!!

最基础的暴力求质数

带一些优化的暴力求质数

通过前面求得的质数对后面的质数进行判断

厄拉多塞筛法

Bitmap对筛法的空间优化(主要是空间优化,当然也有效率优化)

各个求质数方法的运行时间比较
文末全部代码

最基础的暴力求质数


//最基础的暴力求质数(我觉得这个的话,应该就不用多说了)
public static int getPrimes(int n) {
List<Integer> list = new ArrayList<>();
for (int i = 2; i < n; i++) {
boolean bool = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
bool = false;
break;
}
}
if (bool) {
list.add(i);
}
}
// System.out.println(list);
return list.size();
}

带一些优化的暴力求质数

 //带一些优化的暴力求质数
public static int getPrimes1(int n) {
if (n < 3) {
return 0;
}
//从3开始验算,所以初始值为1(2为质数)。
List<Integer> list = new ArrayList<>();
list.add(2);
for (int i = 3; i < n; i++) {
//当某个数为 2 的 n 次方时(n为自然数),其 & (n - 1) 所得值将等价于取余运算所得值
//*如果 x = 2^n ,则 x & (n - 1) == x % n
//if(i % 2 == 0)
if ((i & 1) == 0) {
continue;
}
boolean bool = true;
//用 j * j <= i 代替 j <= i 会更好。
//因为我们已经排除了所有偶数,所以每次循环加二将规避偶数会减少循环次数
for (int j = 3; j * j <= i; j += 2) {
if (i % j == 0) {
bool = false;
break;
}
}
if (bool) {
list.add(i);
}
}
// System.out.println(list);
return list.size();
}

通过前面求得的质数对后面的质数进行判断

 //通过前面求得的质数对后面的质数进行判断
public static int getPrimes2(int n) {
//存放质数得list
List<Integer> list = new ArrayList<>();
//求质数从2开始
for (int m = 2; m < n; m++) {
//声明一个bool变量,看看是不是在list里面有能被整除得
boolean isPrime = true;
//常见得求质数开平方
int sqrt = (int) Math.sqrt(m);
//循环list,list里面都是求过得质数
for (Integer i : list) {
//如果以前得质数能被n整除,说明n不是质数,false,list不能添加n
//直接终止循环
if (m % i == 0) {
isPrime = false;
break;
}
//如果i大于当前这个数得开平方数,证明后面的已经不可能整除了
if (i > sqrt) {
break;
}
}
//如果当前循环内,没有被整除,即为质数,可以加入list,进行下一个循环
if (isPrime) {
list.add(m);
}
}
// System.out.println(list);
return list.size();
}

厄拉多塞筛法

 //厄拉多塞筛法
public static int getPrimes3(int n) {
List<Integer> list = new ArrayList<>();
boolean[] bools = new boolean[n];
for (int i = 2; i < n; i++) {
// 布尔类型的默认值为 假。所以在此处用了逻辑非(!)操作符。
if (!bools[i]) {
list.add(i);
for (int j = i + i; j < n; j += i) {
//只要是i的倍数,就证明不是质数,因为他有其他因子
//排除不是质数的数
bools[j] = true;
}
}
}
// System.out.println(list);
return list.size();
}

Bitmap对筛法的空间优化(主要是空间优化,当然也有效率优化)

 /*
Bitmap对筛法的空间优化(主要是空间优化,当然也有效率优化)

这个的意思就是signs是记录的第几层,每一层分为8个
也就是int为32字节,每个字节是8个bit
(i & 31)==(i % 32)
(1 << (i & 31))这一步是为了满足位数
signs[i / 32]是为了看第几层
((signs[i / 32] & (1 << (i & 31))) == 0证明当前这一层的这一位并没有被记录
说明当前是个质数

循环:
循环中的j就是i的倍数,既然是倍数,就说明他不是质数
signs[j / 32] |= 1 << (j & 31);
在看这里,找到j的那一层,然后看j那一层那几位bit,如果有某一位有1存在,那这一位就是1
二进制下:
101 | 10 == 111
*/
public static int getPrimes4(int n) {
List<Integer> list = new ArrayList<>();
//一个 int 变量占用 32 字节
//如果是在C#中,提供了点阵列(BitArray)数组,那个的可读性会好很多
int[] signs = new int[n / 32 + 1];
for (int i = 2; i < n; i++) {
//将元素和需确定得数字经行按位或运算,如果值改变,说明不存在该数字(未登记该数字),则其为质数。
//(当某个数为 2 的 n 次方时(n为自然数),其 & (n - 1) 所得值将等价于取余运算所得值)
//*如果 x = 2^n ,则 x & (n - 1) == x % n
//下面判断可以写成
//if ((signs[i / size] & (1 << (i % 32))) == 0)
if ((signs[i / 32] & (1 << (i & 31))) == 0) {
list.add(i);
for (int j = i + i; j < n; j += i) {
//登记该数字
signs[j / 32] |= 1 << (j & 31);
}
}
}
// System.out.println(list);
return list.size();
}

最后来看一下各个求质数方法的效果图(这里用的是一百万以内的质数)

面试官手里那些秀你一脸的求质数大法

这里附上全部代码

import java.util.ArrayList;
import java.util.List;

public class Primes {
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println(getPrimes(1000000));
long end = System.currentTimeMillis();
System.out.println("最基础的暴力求质数" + (end - start) + "毫秒");

start = System.currentTimeMillis();
System.out.println(getPrimes1(1000000));
end = System.currentTimeMillis();
System.out.println("带一些优化的暴力求质数" + (end - start) + "毫秒");

start = System.currentTimeMillis();
System.out.println(getPrimes2(1000000));
end = System.currentTimeMillis();
System.out.println("通过前面求得的质数对后面的质数进行判断" + (end - start) + "毫秒");

start = System.currentTimeMillis();
System.out.println(getPrimes3(1000000));
end = System.currentTimeMillis();
System.out.println("厄拉多塞筛法" + (end - start) + "毫秒");

start = System.currentTimeMillis();
System.out.println(getPrimes4(1000000));
end = System.currentTimeMillis();
System.out.println("Bitmap对筛法的空间优化(主要是空间优化,当然也有效率优化)" + (end - start) + "毫秒");

}

//最基础的暴力求质数
public static int getPrimes(int n) {
List<Integer> list = new ArrayList<>();
for (int i = 2; i < n; i++) {
boolean bool = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
bool = false;
break;
}
}
if (bool) {
list.add(i);
}
}
// System.out.println(list);
return list.size();
}

//带一些优化的暴力求质数
public static int getPrimes1(int n) {
if (n < 3) {
return 0;
}
//从3开始验算,所以初始值为1(2为质数)。
List<Integer> list = new ArrayList<>();
list.add(2);
for (int i = 3; i < n; i++) {
//当某个数为 2 的 n 次方时(n为自然数),其 & (n - 1) 所得值将等价于取余运算所得值
//*如果 x = 2^n ,则 x & (n - 1) == x % n
//if(i % 2 == 0)
if ((i & 1) == 0) {
continue;
}
boolean bool = true;
//用 j * j <= i 代替 j <= i 会更好。
//因为我们已经排除了所有偶数,所以每次循环加二将规避偶数会减少循环次数
for (int j = 3; j * j <= i; j += 2) {
if (i % j == 0) {
bool = false;
break;
}
}
if (bool) {
list.add(i);
}
}
// System.out.println(list);
return list.size();
}

//通过前面求得的质数对后面的质数进行判断
public static int getPrimes2(int n) {
//存放质数得list
List<Integer> list = new ArrayList<>();
//求质数从2开始
for (int m = 2; m < n; m++) {
//声明一个bool变量,看看是不是在list里面有能被整除得
boolean isPrime = true;
//常见得求质数开平方
int sqrt = (int) Math.sqrt(m);
//循环list,list里面都是求过得质数
for (Integer i : list) {
//如果以前得质数能被n整除,说明n不是质数,false,list不能添加n
//直接终止循环
if (m % i == 0) {
isPrime = false;
break;
}
//如果i大于当前这个数得开平方数,证明后面的已经不可能整除了
if (i > sqrt) {
break;
}
}
//如果当前循环内,没有被整除,即为质数,可以加入list,进行下一个循环
if (isPrime) {
list.add(m);
}
}
// System.out.println(list);
return list.size();
}

//厄拉多塞筛法
public static int getPrimes3(int n) {
List<Integer> list = new ArrayList<>();
boolean[] bools = new boolean[n];
for (int i = 2; i < n; i++) {
// 布尔类型的默认值为 假。所以在此处用了逻辑非(!)操作符。
if (!bools[i]) {
list.add(i);
for (int j = i + i; j < n; j += i) {
//只要是i的倍数,就证明不是质数,因为他有其他因子
//排除不是质数的数
bools[j] = true;
}
}
}
// System.out.println(list);
return list.size();
}

/*
Bitmap对筛法的空间优化(主要是空间优化,当然也有效率优化)

这个的意思就是signs是记录的第几层,每一层分为8个
也就是int为32字节,每个字节是8个bit
(i & 31)==(i % 32)
(1 << (i & 31))这一步是为了满足位数
signs[i / 32]是为了看第几层
((signs[i / 32] & (1 << (i & 31))) == 0证明当前这一层的这一位并没有被记录
说明当前是个质数

循环:
循环中的j就是i的倍数,既然是倍数,就说明他不是质数
signs[j / 32] |= 1 << (j & 31);
在看这里,找到j的那一层,然后看j那一层那几位bit,如果有某一位有1存在,那这一位就是1
二进制下:
101 | 10 == 111
*/
public static int getPrimes4(int n) {
List<Integer> list = new ArrayList<>();
//一个 int 变量占用 32 字节
//如果是在C#中,提供了点阵列(BitArray)数组,那个的可读性会好很多
int[] signs = new int[n / 32 + 1];
for (int i = 2; i < n; i++) {
//将元素和需确定得数字经行按位或运算,如果值改变,说明不存在该数字(未登记该数字),则其为质数。
//(当某个数为 2 的 n 次方时(n为自然数),其 & (n - 1) 所得值将等价于取余运算所得值)
//*如果 x = 2^n ,则 x & (n - 1) == x % n
//下面判断可以写成
//if ((signs[i / size] & (1 << (i % 32))) == 0)
if ((signs[i / 32] & (1 << (i & 31))) == 0) {
list.add(i);
for (int j = i + i; j < n; j += i) {
//登记该数字
signs[j / 32] |= 1 << (j & 31);
}
}
}
// System.out.println(list);
return list.size();
}
}

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

面试官手里那些秀你一脸的求质数大法

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 面试官手里那些秀你一脸的求质数大法
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏