演算法 - 判斷是否為質數

利用以下 C# 程式碼中的 isPrime(int n) 可以找出 1 ~ 2147483647 之間的質數：

class Prime
{
    static int MAXSIZE = 46340;
    bool[] prime;
    int[] prime_table;
    int prime_table_len;

    public Prime()
    {
        prime_table_len = 0;
        prime = new bool[MAXSIZE + 1];
        prime_table = new int[MAXSIZE];
        initBoolArray(prime);

        for (int i = 3; i <= MAXSIZE; i += 2)
            if (prime[i])
            {
                for (int j = i + i; j <= MAXSIZE; j += i)
                    prime[j] = false;
                prime_table[prime_table_len++] = i;
            }
    }

    public bool isPrime(int n)
    {
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        if (n <= MAXSIZE)
            return prime[n];

        for (int i = 0; i != prime_table_len && 
            prime_table[i] * prime_table[i] <= n; ++i)
            if (n % prime_table[i] == 0)
                return false;
        return true;
    }

    private void initBoolArray(bool[] value)
    {
        int len = value.Length;
        for (int i = 0; i < len; i ++ )
            value[i] = true;
    }
}

回首頁