<<敏捷软件开发：原则、模式与实践>>时,素数产生程序,第一个java
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了<<敏捷软件开发：原则、模式与实践>>时,素数产生程序,第一个java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2354字，纯文字阅读大概需要4分钟。
内容图文
import java.util.Arrays;
public class GeneratePrimes {
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a =generatePrime(1);
System.out.println(Arrays.toString(a));
}
public static int [] generatePrime(int maxValue){
if(maxValue>=2){
int s = maxValue +1;
boolean[] f = new boolean[s];
int i;
for(i = 0;i<s;i++){
f[i]=true;
}
f[0]=f[1]=false;
int j ;
for (i = 2; i <Math.sqrt(s)+1;i++){
for(j = 2 *i;j<s;j+=i){
f[j]=false;
}
}
int count = 0;
for( i = 0;i<s;i++){
if(f[i]){
count++;
}
}
int [] primes = new int[count];
for(i = 0,j = 0;i<s;i++){
if(f[i]){
primes[j++]=i;
}
}
return primes;
}else{
return new int [0];
}
}
}
在看<<敏捷软件开发：原则、模式与实践>>时,素数产生程序,第一个java久把我难了半了,之后找百度搜素数的代码才知道了筛选法求素数.
首先定义了一个布尔类型的数组,初始值全为通过循环全部置为true,而单独将0和1置为false,当发现不是素数的时候将对应的下标改为false,然后将只为true的下标作为值赋值给另一个数组然后输出.(程序是作者故意写这么麻烦的为了将重构码)
重点是中间这个循环想了好久终于想出来为什么了...
for (i = 2; i <Math.sqrt(s)+1;i++){
for(j = 2 *i;j<s;j+=i){
f[j]=false;
}
}
首先说外层循环怎么来的
在这之前先说下普通求素数的套路
最笨的办法就是从2到N-1一个一个暴力的去试.
思考一下其实只要试到2到N/2就好了因为x 如果有(除了自身以外的)质因数，那肯定会小于等于 x/2
在想想除了2以外所有的质因数都是奇数,因此除了2以外试所有的奇数就好了,
在想想会发现因素都是成对出现的比如100,100的因数有：1和100，2和50，4和25，5和20，10和10。想一下,因数肯定一个小于√N一个大于√N.所以只需要试2到√N了.
而这也就是外层循环为什么for (i = 2; i <Math.sqrt(s)+1;i++)的原因
之后说内层循环,设计到了筛选法
我要寻找从1到15里的素数 （红色代表被筛选掉，不是素数）
第1步：1是素数我不用管，不需要筛选掉1的倍数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第2步
：2没有被前面的筛选掉，所以2是素数，然后筛选掉2的倍数 4 6 8 10 12 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第3步：3没有被前面的筛选掉，那么3是素数，然后筛选掉3的倍数 6 9 12 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第4步：4被前面的筛选掉了，不是素数，所以跳过此步骤
第5步：5没有被前面的筛选掉，那么5是素数，然后筛选掉5的倍数 10 15
1 2 3
4
5
6
7
8 9
10
11
12
13
14 15
第6步
：6被前面的筛选了，不是素数，所以跳过此步骤
第7步
：7没有被前面的筛选掉，那么7是素数，然后筛选掉7的倍数 14
1 2 3
4
5
6
7
8 9
10
11
12
13
14 15
第8步
：8被前面的筛选了，不是素数，所以跳过此步骤
第9步
：9被前面的筛选了，不是素数，所以跳过此步骤
第10步
：10被前面的筛选了，不是素数，所以跳过此步骤
第11步
：11没有被前面的筛选掉，那么11是素数，然后筛选掉11的倍数,11的倍数大于15了，没得筛选
第12步
：12被前面的筛选了，不是素数，所以跳过此步骤
第13步
：13没有被前面的筛选掉，那么13是素数，然后筛选掉13的倍数,13的倍数大于15了，没得筛选
第14步
：14被前面的筛选了，不是素数，所以跳过此步骤
第15步：15被前面的筛选了，不是素数，所以跳过此步骤
所以筛选后的结果中，谁是素数显而易见了.
1 2 3
4
5
6
7
8 9
10
11
12
13
14 15
素数是
1 2 3 5 7 11 13
因此内存循环是for(j = 2 *i;j<s;j+=i),2的倍数开始吗 最小是4.
后面的部分转载至 原出处 https://blog.csdn.net/QQ1910084514/article/details/80157263
<敏捷软件开发：原则、模式与实践>>时,素数产生程序,第一个java' ref='nofollow'><<敏捷软件开发：原则、模式与实践>>时,素数产生程序,第一个java
原文：http://blog.51cto.com/10760006/2154780
内容总结
以上是互联网集市为您收集整理的<<敏捷软件开发：原则、模式与实践>>时,素数产生程序,第一个java全部内容，希望文章能够帮你解决<<敏捷软件开发：原则、模式与实践>>时,素数产生程序,第一个java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。