Làm thế nào tôi có thể kiểm tra tính nguyên thủy?

Question

Tôi đang viết một thư viện nhỏ với một số phương pháp liên quan đến số nguyên tố. Như tôi đã làm nền tảng (aka phương pháp làm việc) và bây giờ tôi đang tìm kiếm một số tối ưu hóa. Ofcourse internet là một nơi tuyệt vời để làm như vậy. Tôi đã, tuy nhiên, tình cờ gặp một vấn đề làm tròn và tôi đã tự hỏi làm thế nào để giải quyết điều này. Trong vòng lặp tôi sử dụng để kiểm tra một số cho nó nguyên thủy nó hiệu quả hơn để tìm kiếm cho đến khi sqrt (n) thay vì n/2 hoặc thậm chí n - 1. Nhưng do làm tròn vấn đề một số số bị bỏ qua và do đó một số số nguyên tố bị bỏ qua! Ví dụ: nguyên tố 10000 sẽ là: 104729, nhưng phiên bản 'được tối ưu hóa' kết thúc bằng: 103811.

Một số mã (mở để tối ưu hóa nhiều hơn, tôi biết, nhưng tôi chỉ có thể xử lý một thứ một lần) :

/// <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; 
} 

Tôi biết phần bình phương không thành công (hoặc tôi thất bại), đã thử Math.Ceiling, với kết quả tương tự.

Answer 1

Đáng buồn thay, tôi đã không đã thử các cách tiếp cận thuật toán trước đây. Nhưng nếu bạn muốn thực hiện phương pháp tiếp cận của bạn một cách hiệu quả, tôi khuyên bạn nên làm một số bộ nhớ đệm. Tạo một mảng để lưu trữ tất cả các số nguyên tố nhỏ hơn một ngưỡng xác định, điền vào mảng này và tìm kiếm bên trong/sử dụng nó. Trong ví dụ sau, tìm số liệu là số nguyên tố (1) trong trường hợp tốt nhất (cụ thể là khi số nhỏ hơn hoặc bằng maxPrime, là 821.461 cho bộ đệm 64K) và có phần tối ưu hóa cho các trường hợp khác (bằng cách kiểm tra mod chỉ trên 64K con số trong số 820.000 đầu tiên - khoảng 8%).

(Lưu ý:.. Đừng lấy câu trả lời này là phương pháp "tối ưu" Đó là nhiều hơn một ví dụ về cách để tối ưu hóa thực hiện của bạn)

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; 
    } 
} 

Answer 2

Hãy thử sieve of eratosthenes - điều đó sẽ giải quyết vấn đề về điểm gốc và dấu phẩy động.

Đối với số floor, bạn sẽ được phục vụ tốt hơn bằng cách lấy số ceiling.

Answer 3

Đây là một chức năng nửa phong nha tôi đã viết để giải quyết một trong những 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; 
    } 
} 

Answer 4

Tôi đoán đây là vấn đề của bạn:

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

này cần được

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

do đó bạn không nhận được số vuông làm số nguyên tố. Ngoài ra, bạn có thể sử dụng "idx + = 2" thay vì "idx ++" vì bạn chỉ phải kiểm tra các số lẻ (như bạn đã viết trong nhận xét trực tiếp ở trên ...).

Answer 5

Hãy thử này ...

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 sử dụng này khá một vài lần .. Không nhanh như rây .. nhưng nó hoạt động.

Answer 6

tôi đăng một lớp có sử dụng các sàng hoặc Eratosthenes để tính toán số nguyên tố ở đây:

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

Answer 7

Tôi không biết nếu điều này là khá những gì bạn đang tìm kiếm nhưng nếu bạn đang thực sự quan tâm đến tốc độ sau đó bạn nên nhìn vào các phương pháp probablistic để thử nghiệm nguyên thủy hơn là sử dụng một cái sàng. Rabin-Miller là một thử nghiệm nguyên sinh xác suất được sử dụng bởi Mathematica.

Answer 8

của bạn cho vòng lặp sẽ trông như thế này:

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

Bằng cách đó, bạn tránh dấu chấm động tính toán. Nên chạy nhanh hơn và nó sẽ chính xác hơn. Đây là lý do tại sao câu lệnh for có điều kiện chỉ đơn giản là một biểu thức boolean: nó làm cho những thứ như thế này có thể xảy ra.

Answer 9

Bạn có thể muốn xem xét Fermat's little theorem.

Đây là mã giả từ sách Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, trong đó n là số bạn đang thử nghiệm cho tính nguyên thủy.

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

Thực hiện định lý Fermat sẽ nhanh hơn giải pháp sàng. Tuy nhiên, có những con số Carmichael vượt qua bài kiểm tra của Fermat và KHÔNG phải là thủ tướng. Có giải pháp cho việc này. Tôi khuyên bạn nên tham khảo Section 1.3 in the fore mentioned book. Đó là tất cả về thử nghiệm nguyên thủy và có thể hữu ích cho bạn.

Answer 10

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; 
} 

tôi không thể làm cho nó bất kỳ nhanh hơn ...

Answer 11

Như Mark cho biết, các thử nghiệm Miller-Rabin thực sự là một cách rất tốt để đi. Tham chiếu bổ sung (với mã giả) là Wikipedia article về nó. Cần lưu ý rằng mặc dù nó là xác suất, bằng cách kiểm tra chỉ một số lượng rất nhỏ các trường hợp, bạn có thể xác định xem một số có phải là số nguyên tố cho các số trong phạm vi int (và gần như dài) hay không. Xem this part of that Wikipedia article hoặc the Primality Proving reference để biết thêm chi tiết.

Tôi cũng sẽ khuyên bạn nên đọc this article trên lũy thừa modulo, vì nếu không bạn sẽ được giao dịch với số rất rất lớn khi cố gắng làm bài kiểm tra Miller-Rabin ...

Answer 12

Tôi nghĩ Prime numbers and primality testing là hữu ích và những âm thanh AKS thuật toán thú vị ngay cả khi nó không phải là đặc biệt thực tế so với một thử nghiệm dựa trên probabily.

Answer 13

này hoạt động rất nhanh cho số nguyên tố thử nghiệm (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 

Answer 14

Tôi có một thuật toán nhanh để kiểm tra số nguyên tố. Bạn có thể cải thiện thuật toán nếu bạn biết rằng số nguyên tố ở dạng 6k ± 1, ngoại trừ 2 và 3. Vì vậy, trước tiên bạn có thể kiểm tra xem đầu vào có chia hết cho 2 hay 3. Sau đó, kiểm tra tất cả các số của biểu mẫu 6k ± 1 ≤ √input.

bool IsPrime(int input) 
     { 
      //2 and 3 are primes 
      if (input == 2 || input == 3) 
       return true; 
      else if (input % 2 == 0 || input % 3 == 0) 
       return false;  //Is divisible by 2 or 3? 
      else 
      { 
       for (int i = 5; i * i <= input; i += 6) 
       { 
        if (input % i == 0 || input % (i + 2) == 0) 
         return false; 
       } 
       return true; 
      } 
     } 

Answer 15

Trong trường hợp bất kỳ ai quan tâm, dưới đây là chuyển đổi quy trình của Mohammad ở trên thành VBA. Tôi đã thêm một kiểm tra để loại trừ 1, 0 và số âm khi chúng được định nghĩa là không phải là số nguyên tố.

tôi đã chỉ được thử nghiệm này trong 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