用最少的计算量找到素数的算法

假设您要编写一个函数/方法来查找素数，最有效的方法是什么？我认为这将是一个类似这样的测试：

下面的代码是半c++

bool primeTest (int x) { //X is the number we're testing
    int testUpTo = (int)((sqrt(x))+1);
    for (int i=3; i<testUpTo; i+=2){
        if ((x%i)==0) {
            return false;
        }
    }
    return true;
}

有人有更好的方法来解决这个问题并且需要更少的计算吗？

编辑：稍微更改了代码两次。我写这篇文章时并没有考虑任何特定的语言，尽管由于 bool 这个词，我认为它是 C++ 而不是 java。

我会用米勒拉宾测试 http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test，对于小于 341,550,071,728,321 的数字可以很容易地确定（2^31 比这个小得多）。

伪代码：有许多不同的情况。

1. x小于9：返回(x & 1) != 0 || x == 2
2. x小于约 200（可调整）：使用试除法（您使用的）
3. x小于 1373653：使用底数为 2 和 3 的 Miller Rabin。
4. x小于 4759123141（即其他值）：使用底数为 2、7 和 61 的 Miller Rabin。