让漆黑之眼注视着那微弱的光芒,挣扎却依旧顽强!
C#求素数
上一篇 /
下一篇 2011-03-16 13:43:17
/ 个人分类:C#
说明:所谓素数,就是指能为1与自身所整除的数,例如:2、3、5、7、11等等以此类推;其中该数不可被整除,也不可为偶数;
法1: public string Pri(int n)
{
string s = "";
for (int i = 2; i <= n; i++)
{
bool flag = false;
for (int j = 2; j < i; j++)
{
if (i % j == 0)
{
flag = true;
break;
}
}
if (!flag)
{
s += i + " ";
}
}
return s;
}
以上方法,是最普遍的,也是最容易理解型的,但是相对而言,其性能状况不是很好,由于它需要将每一个数进行循环遍历,以求得素数;所以它所耗费的时间也是相对较长的。下面就介绍了更好的一种方法;
法2: public string Pri2(int n)
{
string s = "2 ";
bool flag;
for (int i = 3; i <= n; i += 2)
{
flag = false;
for (int j = 2; j <= Math.Sqrt(i); j++)
{
if (i % j == 0)
{
flag = true;
break;
}
}
if (!flag)
{
s += i + " ";
}
}
return s;
由于通过此遍历法无法将特殊的素数2读取出来,因此在直接定义了一个字符串类型,将2读取;之后通过开更好求取余下素数;
一般情况下,我们都是考虑先将偶数排除,之后通过遍历算取无法被整除的数;由此我们得出第三种求素数的方法,就是通过数组记录,先排除被整除的数;例如我们需要读取100以内的素数,那么我们可以定义这样一个数组:bool[] num=bool[100];我们知道数组的下标是从0开始计算的,由此我们知道bool[1]=2,我们将其假设为false,那么凡是num[2*i]的数都为False,同样的我们假设bool[2]=3,设其为false,那么num[3*i]的数都为False,以此类推;
总结:根据此例说明, 在一定的实际情况下,可以通过不同角度去衡量空间与时间上的差异,从而找到更适合的方法;
收藏
举报
TAG: