c# 算法

题目：(a) 求1~n内的所有素数。

         (b) 找出一个无序的整数数组内的所有素数。

这两个题目是同样的解法，只不过形式变了一下。这里只对(a)给出解法，(b)类似。

（1）第一种解法

首先明白什么是素数，素数也叫质数，就是只能被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#)：