Question

用C#编写1-100的质数的程序

用C#编写1-100的质数的程序

Answer 1

如要用C#计算1-100之间的所有质数和，所以先必须知道什么是质数?　　
一个数是不是质数“素数”是指除了能被1和自身整除外，不能被任何其它整数整除的自然数。像1，2，3，5，7都是素数。
明白了素数的概念，那么程序就很容易写出来了。要想知道一个数x是否是素数，那么只需要把1~x之间的所有整数来除x，如果存在这么一个数（1和x除外），其能够整除x（余数为0），那么x就不是素数，否则x就是素数。这是从概论出发的解法。那么下面就要看怎么优化了。

其实我们没有必要检查1~x之间的所有整数。只需检查1~[根号x]之间的数就可以了。至于为什么，可以从乘法的角度理解，我们在做除法，其实反过来也就是乘法。我们用判断15是否是素数的情况来举个例子。当我们除3的时候，3*5=15。所以，在判断3的同时也判断了另一个数5。所以我们只需要检查到根号x就可以了，当检查到根号x的时候，根号x之后也检查过了。
代码(c#)：
private static void PrintPrimes(int n)
{

//输出1~n之间的所有素数，n>=3
Console.Write("1 2 ");
int i, j = 0;
for (i = 3; i <= n; i = i + 2)
{
int k = (int)Math.Sqrt(i);
for (j = 2; j <= k; j++)
{
if ((i % j) == 0)
{
break;
}
}

if (j > k)
{
Console.Write(i.ToString() + " ");
}
}
}

PrintPrimes（100）;可打印出1到100的所有质数。
注意for循环