求1~b,求a~b的所有素数
求1~b的所有素数:在求下一个素数N时,可以使用已经求出的素数,仅仅使用它们去模N。这是因为,如果N是合数,它一定可以除尽某个比N小的素数。
求a~b的所有素数:由于求N时,并没有所有的“比N小的素数”存在,所以无法利用上述的技巧。判断的数使用[2,N的开方]的奇数。
2中方法,suShu1()效率是比较快的。(不过,需要在N比较大的情况下。)
public class SuShu {
public static void main(String[] args) {
suShu1(30);
System.out.println("\r\n---------------------");
suShu2(5, 30);
System.out.println("\r\n---------------------");
suShu1(30000);
System.out.println("\r\n---------------------");
suShu2(5, 30000);
}
/**
* 打印[1,b]范围内的所有素数<br>
* 思想:<br>
* 遍历[1,b]范围的所有的奇数n,对每个n,再判断n是否素数:遍历[2,n开方]的素数(这些素数已求出),看是否有模为0的。<br>
* 该方法不同于suShu2()在于“遍历[2,n开方]的素数(这些素数已求出)”,而不是“遍历[2,n开方]的数”,这是因为:<br>
* 如果n是素数,它只有1和n这2个素因子;<br>
* 如果n是合数,它必定有1,n和其他素因子,所以“遍历[2,n开方]的素数(这些素数已求出)”即可;<br>
*/
public static void suShu1(int b) {
int count=0;//记录循环次数
int[] suShu = new int[b/2+1];
suShu[0] = 2;
int index = 1;
for (int n = 3; n <= b; n+=2) {
boolean notSuShu = false;
//遍历[2,n开方]的素数(这些素数已求出)
int i=0;
while(suShu[i]!=0 && suShu[i] <= Math.sqrt(n) && !notSuShu){
count++;
if (n % suShu[i++] == 0) {
notSuShu = true;
}
}
if (!notSuShu) {
suShu[index++] = n;//将求出的素数存储起来
System.out.print(n+" ");
}
}
System.out.print("\n循环最内部的执行次数: "+count);
}
/**
* 打印[a,b]范围内的所有素数<br>
* 思想:<br>
* 遍历[a,b]范围的所有的数n,再判断n是否素数:遍历[2,n开方]的数,看是否有模为0的。<br>
* 判断n是否素数的方法是:遍历[2,n开方]的奇数。<br>
* why n开方?因为<br>
* n = 1 * n<br>
* n = 2 * (n/2)<br>
* n = 3 * (n/3)<br>
* n = 5 * (n/5)<br>
* ...<br>
* n = n开方 * n开方<br>
* ...接下去的就和前面重复了<br>
*/
public static void suShu2(int a, int b) {
int count=0;//记录循环次数
if(a ==1 || a==2){//如果是[1,b]或[2,b],使用suShu1()比较高效!
suShu1(b);
return;
}
if(a % 2 ==0)a++;//将a变成奇数
for (int n = a; n <= b; n+=2) {
boolean notSuShu = false;
//遍历[2,n开方]的奇数
if(n % 2 == 0)notSuShu = true;
for (int i = 3; i <= Math.sqrt(n) && !notSuShu ; i+=2) {
count++;
if (n % i == 0) {
notSuShu = true;
}
}
if (!notSuShu) System.out.print(n+" ");
}
System.out.print("\n循环最内部的执行次数: "+count);
}
}
效果:
3 5 7 11 13 17 19 23 29
循环最内部的执行次数: 26
---------------------
5 7 11 13 17 19 23 29
循环最内部的执行次数: 13
---------------------
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71....
循环最内部的执行次数: 151925
---------------------
5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 ....
循环最内部的执行次数: 253648
分享到:
相关推荐
C语言 求100~200之间的素数 都来下载吧
编程求解1到n之间所有素数之和,输入只有一个n,输出为一个数。
汇编课程设计 求1~5000之间的所有素数 有源代码,有报告,超全~~
求100-200之间的素数,c语言的源代码,方法非常好
java代码-使用java解决求正整数n以内的所有质数个数并给出计算时间的源代码 ——学习参考资料:仅用于个人学习使用!
求100~200内全部素数 自己 写的 一个小程序
求101-200之间的素数; 初学C语言的时候写的程序,写的可能不是很好,但我觉得小白比较能接受,算法很简单。希望可以帮到正在看的你
本书讲解了100个各种类型的Java编程趣味题的求解过程,旨在帮助读者培养编程兴趣,拓宽Java编程思维,提高Java编程能力,掌握用程序设计解决实际问题的方法与技巧。本书取材注重趣味性与实用性,内容涵盖了Java编程...
编写C++程序完成以下功能: (1) 提示用户输入N; (2) 计算出从2到N之间的所有素数; (3) 将结果保存在一个文本文件中。
计算1~1000的质数的程序,实现的算法比较简单。
求1~100间的质数,内含有题目内容,更容易的找到方法
C++求1-n中有多少个质数,最简单易懂!程序十分标准,保准看懂,看不懂的话可以私信我
C/C++语言经典实用趣味程序设计编程百例精解 <br>C/C++语言经典实用趣味程序设计编程百例精解(1) <br>1.绘制余弦曲线 2.绘制余弦曲线和直线 3.绘制圆 4.歌星大奖赛 5.求最大数 6.高次方数...
求任意两个数之间的所有素数,用C语言编程,并包含动态存储,指针等知识点。
Java求100之内的素数,素数是只能被1和自身整除的数,运用for循环和if条件语句,即可轻松解决这个数学问题,求素数也是初学Java时频率较高的测试题,新手看看哦。
求素数的C语言版本 求素数的C语言版本 求素数的C语言版本
在c语言中怎么求109~200间的素数 循环 输出格式怎么每行8个
何为质数: 只能被1 和 自身 整除的数; 方法: 利用js中求模, 看是否有余数. —> 3%2 = 1; 5%2 = 3……… 代码如下: ...那如何判断1到任意数之间的所有质数呢, 就比较简单; 代码如下: function primeNumbe
可以求100 以内的所有素数,可以通过代码中的100改成其他的整数,可以求道其他整数以内的素数
简单的C语言练习,100到200之间的素数,可以举一反三求素数