C#求n以内所有素数的和
时间: 2024-10-09 16:09:12 浏览: 11
在C#中,你可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes)来找到小于等于n的所有素数,并计算它们的和。这是一种古老而高效的算法,其基本思想是从2开始,逐步排除所有的合数,剩下的就是素数。
以下是简单的步骤和代码实现:
1. 创建一个布尔数组`isPrime`,初始全部标记为true,表示每个数字都是潜在的素数。
2. 从2开始遍历到sqrt(n),将`isPrime`数组中的对应索引值为false的数标记为合数。
3. 对于每一个未标记为合数的数i,它就是一个素数,累加到总和`sum`中。
4. 最后,如果n大于2,还需要单独判断n是否是素数,如果是,则添加到总和。
以下是C#代码示例:
```csharp
using System;
using System.Numerics;
public class PrimeSumCalculator
{
public static BigInteger SumOfPrimesBelow(int n)
{
if (n <= 1) return 0; // 素数定义为大于1的自然数
bool[] isPrime = new bool[n + 1];
for (int i = 2; i * i <= n; i++)
{
if (!isPrime[i])
{
for (int j = i * i; j <= n; j += i)
isPrime[j] = true;
}
}
BigInteger sum = 0;
for (int i = 2; i < n; i++)
{
if (!isPrime[i]) continue; // 如果不是素数跳过
sum += i;
}
// 判断n是否为素数并加入(注意n不包括在之前的循环里)
if (isPrime[n])
sum += n;
return sum;
}
public static void Main(string[] args)
{
int n = 50;
Console.WriteLine($"The sum of prime numbers below {n} is: {SumOfPrimesBelow(n)}");
}
}
```