当前位置：首页 > article >正文

C#素数判定算法

article 2025/2/24 20:08:24

在数字的奇妙宇宙中，素数就像是一群神秘的 “纯净使者”。它们只能被 1 和自身整除，简单纯粹，不与其他数字 “纠缠不清”。那我们如何从茫茫数海中，精准地识别出这些 “纯净使者” 呢？这就需要用到素数判定算法啦，它们就像是数字世界的 “火眼金睛”，帮助我们看穿数字的本质。

朴素素数判定算法：最直接的 “挨个排查者”

想象你是一个图书管理员，要从一排书架中找出所有独一无二的珍藏书籍（素数）。最直接的方法就是从第一本书开始，逐一检查它是否只被 1 和自身 “借阅”（整除）。这就是朴素素数判定算法的思路，简单直接，却很 “实在”。

它的原理是：对于一个大于 1 的整数 n，从 2 开始到 n-1，依次检查是否存在能整除 n 的数。如果存在，那么 n 就不是素数；如果不存在，n 就是素数。

using System;
class PrimeNumberChecker
{
 public static bool IsPrime(int number)
 {
 if (number <= 1)
 {
 return false;
 }
 for (int i = 2; i < number; i++)
 {
 if (number % i == 0)
 {
 return false;
 }
 }
 return true;
 }
}

class Program
{
 static void Main()
 {
 int testNumber = 17;
 if (PrimeNumberChecker.IsPrime(testNumber))
 {
 Console.WriteLine($"{testNumber} 是素数");
 }
 else
 {
 Console.WriteLine($"{testNumber} 不是素数");
 }
 }
}

这种算法虽然容易理解和实现，但效率较低。当数字很大时，它需要进行大量的除法运算，就像在巨大的图书馆里一本本翻找，耗费大量时间。时间复杂度为，n 为要判断的数字。

埃拉托色尼筛法：高效的 “批量筛选者”

埃拉托色尼筛法就像是一个聪明的 “图书馆馆长”，他不会一本一本地检查，而是采用一种巧妙的批量筛选策略。

原理是这样的：要找出小于等于 n 的所有素数，先创建一个从 2 到 n 的数字列表。从 2 开始，将 2 的所有倍数（除了 2 本身）都标记为非素数；然后找到下一个未被标记的数字，将其所有倍数也标记为非素数，如此循环，直到所有数字都被处理。最后，未被标记的数字就是素数。

using System;
class SieveOfEratosthenes
{
 public static bool[] GeneratePrimes(int n)
 {
 bool[] isPrime = new bool[n + 1];
 for (int i = 2; i <= n; i++)
 {
 isPrime[i] = true;
 }
 for (int i = 2; i * i <= n; i++)
 {
 if (isPrime[i])
 {
 for (int j = i * i; j <= n; j += i)
 {
 isPrime[j] = false;
 }
 }
 }
 return isPrime;
 }
}

class Program
{
 static void Main()
 {
 int limit = 100;
 bool[] primes = SieveOfEratosthenes.GeneratePrimes(limit);
 Console.WriteLine($"小于等于 {limit} 的素数有:");
 for (int i = 2; i <= limit; i++)
 {
 if (primes[i])
 {
 Console.Write(i + " ");
 }
 }
 }
}

埃拉托色尼筛法的时间复杂度为，大大提高了筛选效率，尤其适用于找出一定范围内的所有素数。它就像用一个高效的过滤器，一次性筛出众多素数。

米勒 - 拉宾素性测试算法：随机的 “概率侦探”

米勒 - 拉宾素性测试算法则像是一个神秘的 “概率侦探”，它采用随机化的方法来判断一个数是否为素数。

它基于费马小定理和二次探测定理，通过多次随机选择一个底数 a，对目标数 n 进行一系列计算和判断。如果在多次测试中，n 都通过了测试，那么 n 是素数的概率就非常高；如果有一次测试不通过，n 就一定是合数。

using System;
class MillerRabinPrimalityTest
{
 private static bool Witness(int a, int n)
 {
 int d = n - 1;
 int s = 0;
 while (d % 2 == 0)
 {
 d >>= 1;
 s++;
 }
 int x = (int)Math.Pow(a, d) % n;
 if (x == 1 || x == n - 1
 {
 return false;
 }
 for (int r = 1; r < s; r++)
 {
 x = (x * x) % n;
 if (x == n - 1)
 {
 return false;
 }
 }
 return true;
 }
 public static bool IsPrime(int n, int k = 5)
 {
 if (n <= 1)
 {
 return false;
 }
 if (n <= 3)
 {
 return true;
 }
 if (n % 2 == 0)
 {
 return false;
 }
 Random random = new Random();
 for (int i = 0; i < k; i++)
 {
 int a = random.Next(2, n - 1);
 if (Witness(a, n))
 {
 return false;
 }
 }
 return true;
 }
}

class Program
{
 static void Main()
 {
 int testNumber = 101;
 if (MillerRabinPrimalityTest.IsPrime(testNumber))
 {
 Console.WriteLine($"{testNumber} 很可能是素数");
 }
 else
 {
 Console.WriteLine($"{testNumber} 不是素数");
 }
 }
}

米勒 - 拉宾素性测试算法的时间复杂度为，其中 k 是测试次数。它虽然是一种概率算法，但在实际应用中，通过适当增加测试次数 k，可以将误判概率降低到极低水平，常用于对大整数的素性判断。