提高代码速度 [英] Improving the speed of code

问题描述

我的代码成功计算了给定数字n之前的素数。但是，我需要一种方法来提高它的速度，因为它对于非常大的数字效率不高。



我尝试了什么：

 public class Solution {
 public static int countPrimes（int n）{
 int count = 0; 
 for（int i = 2; i< n; i ++）{
 if（IsPrime（i））{
 count ++; 
} 
} 
返回计数; 
} 
 public static boolean IsPrime（int num）{
 for（int i = 2; i< = num / 2; i ++）{
 if（num％i == 0）{
返回false; 
} 
} 
返回true 
} 

解决方案

利用常识关于素数。

- 在2之后，所有素数都是奇数，所以不需要测试偶数。

- 所有复数都有一个除以平方根的除数。 / blockquote>

如果你对素数的近似数量感到满意，那么请看一些数学理论，回到欧拉，他给出了一个小于给定数的素数的近似函数的函数。 br />


如果你真的需要精确计数，有更好的方法来查找素数。查看筛选方法和其他方法，其中一些在代码项目中讨论。



通常，为了改进你在这里给出的IsPrime函数，上限为循环的应该是i< = ceiling（sqrt（num）），因为非素数必须有两个因子，其中一个必须小于或等于它的平方根。此外，除以2的除法应该在循环之前，因此循环可以运行：

for（i = 3; i< = ceiling（sqrt（num））; i = i + 2）{...}

那么你只需要测试奇数除数。快两倍。




生成素数列表的方法不止一种。方法比你现在使用的天真方法快得多。我鼓励你使用谷歌作为素数发生器，比如Eratosthenes的Sieve。您不必生成完全停在所需限制的素数列表。您可以生成大于该列表的列表，然后只计算您需要的数字。




My code successfully counts the number of primes before a given number, n. However, I need a way to improve the speed of it as it isn't efficient for extremely large numbers.

What I have tried:



public class Solution {
    public static int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i < n; i++){
            if(IsPrime( i )){
                count++;
            }
        }
        return count;
    }
    public static boolean IsPrime(int num) {
        for(int i=2;i<=num/2;i++){
            if(num % i == 0){
                return false;
            }
        }
        return true
}

解决方案

Take advantage of common knowledge about prime numbers.
- After 2, all primes are odd, so no need to test even numbers.
- All compound numbers have a divisor below its square root.




If you can be satisfied with an approximate number of primes, look into some math theory, going back to Euler, who gave a function for the approximate number of primes less than a given number.

If you really need the exact count, there are better ways to find prime numbers. Look into the sieve methods and others, some of which are discussed here on code project.

Trivially, to improve the IsPrime function you have given here, the upper bound of the for loop should be i <= ceiling(sqrt(num)), because a non-prime number must have two factors, and one of them must be less than or equal to its square root. Also, the division by two should come before the loop, so then the loop may run:
for (i=3; i<=ceiling(sqrt(num)); i=i+2) { ...}
So then you only have to test odd divisors. Twice as fast.




There's more than one way to generate a list of primes. Methods that are FAR faster than the naive method you're using now. I encourage you to Google for prime number generators, like the Sieve of Eratosthenes. You don't have to generate a list of primes that stops exactly at the limit you want. You can generate a list larger than that and then only count up to the number you need.




这篇关于提高代码速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！