读书人

写了一个数最小质因数的算法求

发布时间: 2013-10-30 12:56:21 作者: rapoo

写了一个求一个数最小质因数的算法求高手指点


/**
* 求最小质因数
*/

public static int minPrimeYinShu(int n){
t++;
//判断是否为质数
if(isPrime(n) && 1==t){
return n;
}

//获取n的开方,并取整
Double d = new Double(Math.sqrt(n));
int m = d.intValue();

//如果这里m为质数,并且能被n整除
if(isPrime(m) && n%m==0){
int temp = n/m;

//这里temp一定会比m大
if(Prime.isPrime(temp)){
return m;//递归出口!
}else {
return minPrimeYinShu(temp);
}
}
//直到m能被整除
while(n%m!=0){
whilekey++;
m--;
}
if(isPrime(m) && n%m==0){
int temp = n/m;
//这里temp一定会比m大
if(Prime.isPrime(temp)){
return m;//递归出口!
}else {
return minPrimeYinShu(temp);
}
}

return minPrimeYinShu(m);
}
/**
* 判断是否为素数
* @param n 待判断整数
* @return 布尔类型
*/
public static boolean isPrime(int n){
if(2 > n){
return false;
}
boolean isPrime = true;
for(int i=2; i<=Math.sqrt(n); i++){
if((0==n%i) || (n<2)){
isPrime = false;
}
}
return isPrime;
}
算法 java
[解决办法]
public static boolean isPrime(int n){
if(2 > n){
return false;
}
boolean isPrime = true;
for(int i=2; i<=Math.sqrt(n); i++){
if((0==n%i)
[解决办法]
(n<2)){
isPrime = false;
}
}
return isPrime;
}
这个方法已经够精简了。但是要是把
if((0==n%i)
[解决办法]
(n<2)){
isPrime = false;
}
改成
return false;能省不少运算次数。。

另外我想想有没有什么能结合的方法,你的每个运算都是分开的,这样编程是对的。但是求最后的结果有可能会导致运算次数增多。。

读书人网 >J2SE开发

热点推荐