写的一个素数求解程序,用了4种方法,有测试时间,欢迎讨论 - 黑马程序员技术交流社区

class prime {
static void prt(String s){
System.out.print(s);
}
/*
基本思想:
1.合数都可以彻底分解为质数与质数的乘积,即合数总是可以找到至少一个质数使得这个合数%素数==0
2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有素数),如果没有一个能除尽,则x是素数
3.任何合数成对的因数中,必然有一个小于等于这个数开方的根,例如sqrt(12)=3.4,12=2*6=3*4,2和3都小于3.4
所以只需要比较到sqrt(x)就可以确定这个数是不是素数了
基于以上思想,创建一个数组由小到大存储已经确认的素数,即存储,也用来运算,代价是要使用比较多的内存
*/
private static void primeTest1(int a){
int i = 0;
int j = 0;
int sqrtNum = 0;
int arryNum = (int)(a*1.2/Math.log((double)a));
int prim[] = new int[arryNum]; //创建一个数组
for(i = 0;i<arryNum;i++)
prim[i] = i+2; //数组初始化,prim[0] = 2...
int countNum = 2; //已经有2,3 这2个素数
long startTime=System.currentTimeMillis();//用于计时
for(i=5;i<a;i+=2){ //从5开始,步长为2,直接排除偶数参与运算
sqrtNum = (int)Math.sqrt(i); //计算i开方的值,转换为int型
for(j=1;j<=countNum;j++){ //prim[0]=2,prim[1]=3,已排除偶数,故从3开始参与运算,
if((i%(prim[j]))==0) //i被prim中存储的素数除尽,证明它不是素数,跳出循环
break;
if( prim[j] > sqrtNum ){ //除数的素数值已经大于被除数的开方值,判断这个数是素数
prim[countNum] = i; //存储
countNum++; //
break; //完成质数的确认,跳出循环
}
}
}
System.out.println("\nTest1 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
i = 0;
System.out.println("countNum : " + countNum); //打印素数总数
// while(i<count){ //打印每个素数
// System.out.print(prim[i]+"\t");
// i++;
// }
}
/*
基本思想:
1.所有素数一定是奇数,因为偶数可以被2整除
2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有奇数),如果没有一个能除尽,则x是素数
3.任何合数成对的因数中,必然有一个小于等于这个数开方的根,例如sqrt(12)=3.4,12=2*6=3*4,2和3都小于3.4
所以只需要比较到sqrt(x)就可以确定这个数是不是素数了
*/
private static void primeTest2(int a){
int i;
int j;
int countNum = 2;
int sqrtNum =0;
// System.out.print("2\t3\t"); //需要输出解除注释,
long startTime=System.currentTimeMillis();
for( i = 5;i<a;i+=2){ //从5开始,步长为2,直接排除偶数参与运算
sqrtNum = (int)Math.sqrt(i);
for(j = 3;j<i;j+=2){
if(i%j ==0)
break;
if(j > sqrtNum){
countNum++;
// System.out.print(i + "\t"); //需要输出解除注释,
break;
}
}
}
System.out.println("\nTest2 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
System.out.println("countNum : " + countNum);
}
/*
基本思想:
1.所有素数一定是奇数,因为偶数可以被2整除
2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有奇数),如果没有一个能除尽,则x是素数
*/
private static void primeTest3(int a){
int i;
int j;
int countNum = 2;
// System.out.print("2\t3\t"); //需要输出解除注释,
long startTime=System.currentTimeMillis();
for( i = 5;i<a;i+=2){ //从5开始,步长为2,直接排除偶数参与运算
for(j = 3;j<i;j+=2){
if(i%j ==0)
break;
if(j+2 == i){
countNum++;
// System.out.print(i + "\t"); //需要输出解除注释,
break;
}
}
}
System.out.println("\nTest3 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
System.out.println("countNum : " + countNum);
}
/*
基本思想:
拿到任意一个在取值范围以内的数字x,用x%(比x小的所有数),如果没有一个能除尽,则x是素数
*/
private static void primeTest4(int a){
int i;
int j;
int countNum = 1; //此时默认2是素数
// System.out.print("2\t");
long startTime=System.currentTimeMillis();
for( i = 3;i<a;i++){ //从3开始,因为2%2==0,会影响判断
for(j = 2;j<i;j++){
if(i%j ==0)
break;
if(j+1 == i){ //判断到比i小1,这时可以确认它是素数
countNum++;
// System.out.print(i + "\t"); //需要输出解除注释,
break;
}
}
}
System.out.println("\nTest4 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
System.out.println("countNum : " + countNum);
}
/*
*/
public static void main(String args[]) {
int maxNum = 300000; //通过这里设置取值上限,完成4种方法运行时间的实验
prt("Hello Cruel World!\n");
primeTest1(maxNum);
primeTest2(maxNum);
primeTest3(maxNum);
primeTest4(maxNum);
}
}

复制代码