试图找到一个数的最大质因数
Trying to find the greatest prime factor of a number
我是一名初级程序员,我刚刚接受了一项挑战,要找出一个非常大的数中的最大质数。但是我一直在尝试编写代码来找到解决方案,但我没有任何运气。这是我最后一次尝试
public class primeNums {
public static void main(String [] args) {
int num = 100000;
int rem = 0;
int prime = 0;
boolean isPrime = true;
int j = 2;
for(int i = 1;i < num;++i) { //Outer loop to find the factor of the num.
rem = num % i;
if((rem == 0)&&(i != 1)) { //Checking if i is a factor.
while((j <= i) && (isPrime)) { //Inner loop trying to find if i is prime.
if((i % j) == 0) { //Checking if i/j has any remainders.
isPrime = false; //If there isn't any remainders, i isn't
//prime, isPrime, is false and exists the
//inner loop.
}
else { //If i/j has any remainders, continue the
//loop and print the value of i (a test).
isPrime = true;
System.out.println(i);
}
++j; //Increment j until inner loop condition
} //becomes false.
}
}
}
}
几个问题:
- 当 i 有一个新值时,您没有将 j 重置回 2,这意味着您没有测试对于所有除数。
- 当你有一个新值 i;
时,你不会将 isPrime 重置为 false
- 你让 j 达到与 i 相同的值,它总是被认为是除数,所以 [= 没有值19=]i 将被认为是素数;
- 你不应该仅仅因为你发现 j 的一个值不是我。只有当 none 的 j 的值除以 i 时,你才应该这样做。因此,您只能在考虑 j;
的所有值后才能决定
这是对您的代码的建议更正:
int num = 100000;
int factor = 0;
int rem = 0;
int prime = 0;
boolean isPrime = true;
int j = 2;
for(int i = 1;i < num;++i) {
rem = num % i;
if((rem == 0)&&(i != 1)) {
j = 2; // set j back to start
isPrime = true; // assume prime before iterating
while(j < i && isPrime) { // don't let j become equal to i
if((i % j) == 0) {
isPrime = false;
} // don't set isPrime to true until you have completed all iterations
++j;
}
if (isPrime) { // now is the time to check!
prime = i; // remember this prime
}
}
}
// output result
System.out.println("largest prime divisor: " + prime);
虽然这可行但不是最优的:您可以停止寻找除数 j 直到 i 的平方根。出于同样的原因,i 不必比 num 的平方根增加得更多。
我是一名初级程序员,我刚刚接受了一项挑战,要找出一个非常大的数中的最大质数。但是我一直在尝试编写代码来找到解决方案,但我没有任何运气。这是我最后一次尝试
public class primeNums {
public static void main(String [] args) {
int num = 100000;
int rem = 0;
int prime = 0;
boolean isPrime = true;
int j = 2;
for(int i = 1;i < num;++i) { //Outer loop to find the factor of the num.
rem = num % i;
if((rem == 0)&&(i != 1)) { //Checking if i is a factor.
while((j <= i) && (isPrime)) { //Inner loop trying to find if i is prime.
if((i % j) == 0) { //Checking if i/j has any remainders.
isPrime = false; //If there isn't any remainders, i isn't
//prime, isPrime, is false and exists the
//inner loop.
}
else { //If i/j has any remainders, continue the
//loop and print the value of i (a test).
isPrime = true;
System.out.println(i);
}
++j; //Increment j until inner loop condition
} //becomes false.
}
}
}
}
几个问题:
- 当 i 有一个新值时,您没有将 j 重置回 2,这意味着您没有测试对于所有除数。
- 当你有一个新值 i; 时,你不会将 isPrime 重置为
- 你让 j 达到与 i 相同的值,它总是被认为是除数,所以 [= 没有值19=]i 将被认为是素数;
- 你不应该仅仅因为你发现 j 的一个值不是我。只有当 none 的 j 的值除以 i 时,你才应该这样做。因此,您只能在考虑 j; 的所有值后才能决定
false
这是对您的代码的建议更正:
int num = 100000;
int factor = 0;
int rem = 0;
int prime = 0;
boolean isPrime = true;
int j = 2;
for(int i = 1;i < num;++i) {
rem = num % i;
if((rem == 0)&&(i != 1)) {
j = 2; // set j back to start
isPrime = true; // assume prime before iterating
while(j < i && isPrime) { // don't let j become equal to i
if((i % j) == 0) {
isPrime = false;
} // don't set isPrime to true until you have completed all iterations
++j;
}
if (isPrime) { // now is the time to check!
prime = i; // remember this prime
}
}
}
// output result
System.out.println("largest prime divisor: " + prime);
虽然这可行但不是最优的:您可以停止寻找除数 j 直到 i 的平方根。出于同样的原因,i 不必比 num 的平方根增加得更多。