英文:
Advice on speeding up prime number counter
问题
以下是改进后的代码:
public static int countPrime(int limitNo) {
int noOfTimes = 0;
for (int o = 2; o <= limitNo; o++) {
boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(o); i++) {
if (o % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
noOfTimes++;
}
}
return noOfTimes;
}
英文:
How can I improve the logic of the following code? The purpose is to compute the number of primes from 1 to the user input (limitNo). The program works fine except it takes a while, more than the usual 1-3 secs, to generate a result for huge numbers like 99999.
public static int countPrime(int limitNo) {
int noOfTimes = 0, noOfRounds = 0; int o = 1;
while (o <= limitNo) {
for (int i = 1; i <= o; i++) {
if (o%i == 0) {
noOfRounds++;
}
}
if (noOfRounds == 2) {
noOfTimes++;
}
noOfRounds = 0;
o++;
}
return noOfTimes;
}
答案1
得分: 1
以下是翻译好的内容:
代码可以通过以下方式进行改进:
- 将部分代码行分离,以创建一个
isPrime()
方法。 - 修改
for
循环的限制条件,这样如果条件满足,意味着该数字不是质数。
public static boolean isPrime(int num) {
for (int i = 2; i < num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
- 将方法中的代码替换为
isPrime()
并更改起始值int o = 2;
。
public static int countPrime(int limitNo) {
int noOfTimes = 0;
int o = 2;
while (o <= limitNo) {
if (isPrime(o)) {
noOfTimes++;
}
o++;
}
return noOfTimes;
}
- 当然,还有更好的改进方法,例如:
for (int i = 2; i <= num/2; i++)
for (int i = 2; i <= Math.sqrt(num); i++)
英文:
The code can be improved by
-
Separating some of the lines to make an
isPrime()
method. -
Changing limits of the
for
loop so that if the condition is met that means the number is not prime.public static boolean isPrime(int num) { for ( int i = 2 ; i < num ; i++ ) { if ( num % i == 0 ) { return false; } } return true; }
-
Replacing the code in the method with
isPrime()
and change the startint o = 2 ;
.public static int countPrime(int limitNo) { int noOfTimes = 0; int o = 2; while ( o <= limitNo ) { if ( isPrime(o) ) { noOfTimes++; } o++; } return noOfTimes; }
-
Of course, there are better and more improvements like:
for ( int i = 2 ; i <= num/2 ; i++ )
for ( int i = 2 ; i <= Math.sqrt(num) ; i++ )
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论