c# - 我如何测试素数？

Question

我正在编写一个带有一些素数相关方法的小库。由于我已经完成了基础工作（又名工作方法），现在我正在寻找一些优化。当然，互联网是这样做的好地方。然而，我偶然发现了一个舍入问题，我想知道如何解决这个问题。

在循环中，我用来测试一个数字的素数，搜索直到 sqrt(n) 而不是 n/2 甚至 n - 1 更有效。但是由于舍入问题，一些数字被跳过，因此一些素数被跳过！例如，第 10000 个素数应为：104729，但“优化”版本最终为：103811。

一些代码（我知道它可以进行更多优化，但我一次只能处理一件事）：

/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
    // 0 and 1 are not prime numbers
    if (test == 0 || test == 1) return false;

    // 2 and 3 are prime numbers
    if (test == 2) return true;

    // all even numbers, save 2, are not prime
    if (test % 2 == 0) return false;

    double squared = Math.Sqrt(test);
    int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));

    // start with 5, make increments of 2, even numbers do not need to be tested
    for (int idx = 3; idx < flooredAndSquared; idx++)
    {
        if (test % idx == 0)
        {
            return false;
        }
    }
    return true;
}

I know the squared part fails me (or I fail), tried Math.Ceiling as well, with about the same results.

score 10 · Accepted Answer

I guess this is your problem:

for (int idx = 3; idx < flooredAndSquared; idx++)

This should be

for (int idx = 3; idx <= flooredAndSquared; idx++)

so you don't get square numbers as primes. Also, you can use "idx += 2" instead of "idx++" because you only have to test odd numbers (as you wrote in the comment directly above...).

score 10 · Accepted Answer

I don't know if this is quite what you are looking for but if you are really concerned about speed then you should look into probablistic methods for testing primality rather than using a sieve. Rabin-Miller is a probabilistic primality test used by Mathematica.

score 8 · Accepted Answer

Sadly, I haven't tried the algorithmic approaches before. But if you want to implement your approach efficiently, I'd suggest doing some caching. Create an array to store all prime numbers less than a defined threshold, fill this array, and search within/using it.

In the following example, finding whether a number is prime is O(1) in the best case (namely, when the number is less than or equal to maxPrime, which is 821,461 for a 64K buffer), and is somewhat optimized for other cases (by checking mod over only 64K numbers out of the first 820,000 -- about 8%).

(Note: Don't take this answer as the "optimal" approach. It's more of an example on how to optimize your implementation.)

public static class PrimeChecker
{
    private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB

    private static int[] primes;
    public static int MaxPrime { get; private set; }

    public static bool IsPrime(int value)
    {
        if (value <= MaxPrime)
        {
            return Array.BinarySearch(primes, value) >= 0;
        }
        else
        {
            return IsPrime(value, primes.Length) && IsLargerPrime(value);
        }
    }

    static PrimeChecker()
    {
        primes = new int[BufferSize];
        primes[0] = 2;
        for (int i = 1, x = 3; i < primes.Length; x += 2)
        {
            if (IsPrime(x, i))
                primes[i++] = x;
        }
        MaxPrime = primes[primes.Length - 1];
    }

    private static bool IsPrime(int value, int primesLength)
    {
        for (int i = 0; i < primesLength; ++i)
        {
            if (value % primes[i] == 0)
                return false;
        }
        return true;
    }

    private static bool IsLargerPrime(int value)
    {
        int max = (int)Math.Sqrt(value);
        for (int i = MaxPrime + 2; i <= max; i += 2)
        {
            if (value % i == 0)
                return false;
        }
        return true;
    }
}

score 5 · Accepted Answer

I posted a class that uses the sieve or Eratosthenes to calculate prime numbers here:

Is the size of an array constrained by the upper limit of int (2147483647)?

score 4 · Accepted Answer

As Mark said, the Miller-Rabin test is actually a very good way to go. An additional reference (with pseudo-code) is the Wikipedia article about it.

It should be noted that while it is probabilistic, by testing just a very small number of cases, you can determine whether a number is prime for numbers in the int (and nearly long) range. See this part of that Wikipedia article, or the Primality Proving reference for more details.

I would also recommend reading this article on modular exponentiation, as otherwise you're going to be dealing with very very large numbers when trying to do the Miller-Rabin test...

score 3 · Accepted Answer

You might want to look into Fermat's little theorem.

Here is the pseudo code from the book Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, where n is the number you are testing for primality.

Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
   return yes
else
   return no

Implementing Fermat's theorem should be faster then the sieve solution. However, there are Carmichael numbers that pass Fermat's test and are NOT prime. There are workarounds for this. I recommend consulting Section 1.3 in the fore mentioned book. It is all about primality testing and might be helpful for you.

score 1 · Accepted Answer

Here is a halfway decent function I wrote to solve one of the Euler:

private static long IsPrime(long input)
{
    if ((input % 2) == 0)
    {
        return 2;
    }
    else if ((input == 1))
    {
        return 1;
    }
    else
    {
        long threshold = (Convert.ToInt64(Math.Sqrt(input)));
        long tryDivide = 3;
        while (tryDivide < threshold)
        {
            if ((input % tryDivide) == 0)
            {
                Console.WriteLine("Found a factor: " + tryDivide);
                return tryDivide;
            }
            tryDivide += 2;
        }
        Console.WriteLine("Found a factor: " + input);
        return -1;
    }
}

score 1 · Accepted Answer

Try this...

if (testVal == 2) return true;
if (testVal % 2 == 0) return false;

for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
   if (testVal % i == 0)
       return false;
}

return true;

Ive used this quite a few times.. Not as fast as a sieve.. but it works.

score 1 · Accepted Answer

First and foremost, primes start from 2. 2 and 3 are primes. Prime should not be dividable by 2 or 3. The rest of the primes are in the form of 6k-1 and 6k+1. Note that you should check the numbers up to SQRT(input). This approach is very efficient. I hope it helps.

public class Prime {

    public static void main(String[] args) {
        System.out.format("%d is prime: %s.\n", 199, isPrime(199)); // Prime
        System.out.format("%d is prime: %s.\n", 198, isPrime(198)); // Not prime
        System.out.format("%d is prime: %s.\n", 104729, isPrime(104729)); // Prime
        System.out.format("%d is prime: %s.\n", 104727, isPrime(982443529)); // Prime
    }

    /**
     * Tells if a number is prime or not.
     *
     * @param input the input
     * @return If the input is prime or not
     */
    private boolean isPrime(long input) {
    if (input <= 1) return false; // Primes start from 2
    if (input <= 3) return true; // 2 and 3 are primes
    if (input % 2 == 0 || input % 3 == 0) return false; // Not prime if dividable by 2 or 3
    // The rest of the primes are in the shape of 6k-1 and 6k+1
    for (long i = 5; i <= Math.sqrt(input); i += 6) if (input % i == 0 || input % (i + 2) == 0) return false;
    return true;
    }

}

score 1 · Accepted Answer

Repeat mode operations will run very slowly. Use the eratosthenes grid to get the prime list in order.

/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new MyBitArray(limit, true);
for (long i = 2; i < limit; i++)
    if (numbers[i])
        for (long j = i * 2; j < limit; j += i)
            numbers[j] = false;
        }

public class MyBitArray: IDisposable
    {
        byte[] bytes;
        public MyBitArray(long limit, bool defaultValue = false)
        {
            long byteCount = (limit & 7) == 0 ? limit >> 3 : (limit >> 3) + 1;
            this.bytes = new byte[byteCount];
            for(long i = 0; i < byteCount; i++)
            {
                bytes[i] = (defaultValue == true ? (byte)0xFF : (byte)0x00);
            }
            this.limit = limit;
        }

        public MyBitArray(long limit, byte[] bytes)
        {
            this.limit = limit;
            this.bytes = bytes;
        }

        public bool this[long index]
        {
            get
            {
                return getValue(index);
            }
            set
            {
                setValue(index, value);
            }
        }
        
        bool getValue(long index)
        {
            if (index < 8)
            {
                return getBit(bytes[0], (byte)index);
            }

            long byteIndex = (index & 7) == 0 ? ((index >> 3) - 1) : index >> 3;
            byte bitIndex = (byte)(index & 7);
            return getBit(bytes[byteIndex], bitIndex);
        }
        void setValue(long index, bool value)
        {
            if (index < 8)
            {
                bytes[0] = setBit(bytes[0], (byte)index, value);
                return;
            }

            long byteIndex = (index & 7) == 0 ? (index >> 3) - 1 : index >> 3;
            byte bitIndex = (byte)(index & 7);
            
            bytes[byteIndex] = setBit(bytes[byteIndex], bitIndex, value);
        }

        bool getBit(byte byt, byte index)
        {
            return ((byt & (1 << index)) >> index) == 1;
        }

        byte setBit(byte byt, byte index, bool value)
        {
            return (byte)((byt & ~(1 << index)) + (value ? 1 << index : 0));
        }

        public void Dispose()
        {
            GC.Collect(2, GCCollectionMode.Optimized);
        }

        private long limit;
        public long Limit { get { return limit; } }
        public byte[] Bytes { get { return this.bytes; } } 
    }

However, I would suggest you a much better method for prime number testing. For 64 bit numbers, no matter how large the number is, it gives the exact result in milliseconds.

public static bool IsPrime(ulong number)
{
    return number == 2 
        ? true 
        : (BigInterger.ModPow(2, number, number) == 2 
            ? (number & 1 != 0 && BinarySearchInA001567(number) == false) 
            : false)
}

public static bool BinarySearchInA001567(ulong number)
{
    // Is number in list?
    // todo: Binary Search in A001567 (https://oeis.org/A001567) below 2 ^ 64
    // Only 2.35 Gigabytes as a text file http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
}

score 0 · Accepted Answer

Try the sieve of eratosthenes -- that should take out getting the root and floating point issues.

As for the floor, you will be better served by taking the ceiling.

score 0 · Accepted Answer

private static bool IsPrime(int number) {
    if (number <= 3)
        return true;
    if ((number & 1) == 0)
        return false;
    int x = (int)Math.Sqrt(number) + 1;
    for (int i = 3; i < x; i += 2) {
        if ((number % i) == 0)
            return false;
    }
    return true;
}

I can't get it any faster...

score 0 · Accepted Answer

I thought Prime numbers and primality testing was useful and the AKS algorithm sounds interesting even if it isn't particularly practical compared to a probabily based tests.

score 0 · Accepted Answer

This works very fast for testing primes (vb.net)

Dim rnd As New Random()
Const one = 1UL

    Function IsPrime(ByVal n As ULong) As Boolean
        If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then
           return false
        End If

        Dim s = n - one

        While s Mod 2 = 0
            s >>= one
        End While

        For i = 0 To 10 - 1
            Dim a = CULng(rnd.NextDouble * n + 1)
            Dim temp = s
            Dim m = Numerics.BigInteger.ModPow(a, s, n)

            While temp <> n - one AndAlso m <> one AndAlso m <> n - one
                m = (m * m) Mod n
                temp = temp * 2UL
            End While

            If m <> n - one AndAlso temp Mod 2 = 0 Then
                Return False
            End If
        Next i

        Return True
    End Function

score 0 · Accepted Answer

In case anyone else is interested, here's my conversion of Mohammad's procedure above to VBA. I added a check to exclude 1, 0, and negative numbers as they are all defined as not prime.

I have only tested this in Excel VBA:

Function IsPrime(input_num As Long) As Boolean
    Dim i As Long
    If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime.
        IsPrime = False: Exit Function
    ElseIf input_num = 2 Then
        IsPrime = True: Exit Function '2 is a prime
    ElseIf input_num = 3 Then
        IsPrime = True: Exit Function '3 is a prime.
    ElseIf input_num Mod 2 = 0 Then
        IsPrime = False: Exit Function 'divisible by 2, so not a prime.
    ElseIf input_num Mod 3 = 0 Then
        IsPrime = False: Exit Function 'divisible by 3, so not a prime.
    Else
        'from here on, we only need to check for factors where
        '6k ± 1 = square root of input_num:
        i = 5
        Do While i * i <= input_num
            If input_num Mod i = 0 Then
                IsPrime = False: Exit Function
            ElseIf input_num Mod (i + 2) = 0 Then
                IsPrime = False: Exit Function
            End If
            i = i + 6
        Loop
        IsPrime = True
    End If
End Function

score -3 · Accepted Answer

Your for loop should look like this:

for (int idx = 3; idx * idx <= test; idx++) { ... }

That way, you avoid floating-point computation. Should run faster and it'll be more accurate. This is why the for statement conditional is simply a boolean expression: it makes things like this possible.

c# - 我如何测试素数？

16 回答 16

Related

Reference