求质数的几种算法
2025-05-28 21:21:47The most efficient algorithm for determining whether a number is prime involves several optimizations over the basic trial division method. The most widely used and efficient methods include:
1. Trial Division (Optimized)
Time Complexity: O(n)O(\sqrt{n})O(n)
Description: Instead of checking all numbers from 2 to n−1n-1n−1 to see if they divide nnn, you can limit the checks to numbers up to n\sqrt{n}n. If nnn is divisible by any number up to n\sqrt{n}n, it's not prime. This reduces the number of checks significantly.
Optimizations:
Only check numbers from 2 to n\sqrt{n}n.
Skip even numbers greater than 2 (since all even numbers other than 2 are not prime).
Skip multiples of 3 by checking 6k±16k \pm 16k±1 numbers, since all primes greater than 3 are of the form 6k±16k \pm 16k±1.
bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true; // 2 is prime
if (n % 2 == 0) return false; // no even numbers except 2 are prime
for (int i = 3; i * i <= n; i += 2) { // Check only odd divisors
if (n % i == 0) return false;
}
return true;
}
GPT还提到了另外3个，但是好像不怎么使用
Summary of Best Practices:
For small numbers: Use the Optimized Trial Division method.
For generating primes up to a limit NNN: Use the Sieve of Eratosthenes.
For large numbers (e.g., cryptographic applications): Use the Miller-Rabin Primality Test for fast probabilistic testing or AKS for deterministic testing.
https://blog.sina.com.cn/s/blog_622e77cc0100n5lm.html
1、根据质数的定义求 质数定义：只能被1或者自身整除的自然数（不包括1），称为质数。 利用它的定义可以循环判断该数除以比它小的每个自然数（大于1），如果有能被它整除的，则它就不是质数。对应代码是：
///
/// 输出从2到max的所有质数
///
///
public static void Prime(int max)
{
bool flag = false;
int count = 0;
for (int i = 2; i <= max; i++)
{
flag = IsPrime(i);
if (flag)
{
Console.Write("{0,3} ",i);
count++;
if (count % 8 == 0)
{
Console.WriteLine();
}
}
}
}
///
/// 判断输入的数字是否是质数
///
///
///
public static bool IsPrime(int n)
{
bool flag = true;
if (n < 2)
{
throw new ArgumentOutOfRangeException();
}
for (int i = 2; i <= n - 1; i++)
{
if (n % i == 0)
{
flag = false;
break;
}
}
return flag;
}
2、利用一个定理——如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。例如：50，最小质因数是2，2<50的开根号再比如：15，最小质因数是3，3<15的开根号 合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数，则它是质数。 上面的定理是说，如果一个数能被它的最小质因数整除的话，那它肯定是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开跟后后的所有数整除，这样做的运算就会少了很多，因此效率也高了很多。对应代码是：
只需要将之前的质数判断更改一下就可以了
///
/// 判断输入的数字是否是质数
///
///
///
public static bool IsPrime(int n)
{
bool flag = true;
if (n < 2)
{
throw new ArgumentOutOfRangeException();
}
int max = Convert.ToInt32(Math.Floor(Math.Sqrt(n)));
for (int i = 2; i <= max; i++)
{
if (n % i == 0)
{
flag = false;
break;
}
}
return flag;
}
3、筛法求质数，效率最高，但会比较浪费内存 首先建立一个boolean类型的数组，用来存储你要判断某个范围内自然数中的质数，例如，你要输出小于200的质数，你需要建立一个大小为201（建立201个存储位置是为了让数组位置与其大小相同）的boolean数组，初始化为true。 其次用第二种方法求的第一个质数（在此是2），然后将是2的倍数的数全置为false（2除外），即2、4、6、8……位置上置为false。然后是3的倍数的全置为false（3除外），一直到14（14是200的开平方），这样的话把不是质数的位置上置为false了，剩下的全是质数了，挑着是true的打印出来就行了。对应代码是：
///
/// 输出从2到n的所有质数
///
///
public static void Prime(int n)
{
bool[] array = new bool[n + 1].Select(x => x = true).ToArray();
array[1] = false;
int count = 0;
int sqrt = Convert.ToInt32(Math.Floor(Math.Sqrt(n)));
for (int i = 2; i <= sqrt; i++)
{
for (int j = i; j * i <= n; j++)
{
array[j * i] = false;
}
}
for (int i = 1; i <= n; i++)
{
if (array[i])
{
Console.Write("{0,3} ", i);
count++;
if (count % 8 == 0)
{
Console.WriteLine();
}
}
}
}
天下足球世界杯