如何用mysql求质数_求质数的几种算法
http://blog.sina.com.cn/s/blog_622e77cc0100n5lm.html
1、根据质数的定义求
质数定义：只能被1或者自身整除的自然数(不包括1)，称为质数。
利用它的定义可以循环判断该数除以比它小的每个自然数(大于1)，如果有能被它整除的，则它就不是质数。
对应代码是：
///
///输出从2到max的所有质数///
///
public static void Prime(intmax)
{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(intn)
{bool flag = true;if (n < 2)
{throw newArgumentOutOfRangeException();
}for (int i = 2; i <= n - 1; i++)
{if (n % i == 0)
{
flag= false;break;
}
}returnflag;
}
2、利用一个定理——如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。例如：50，最小质因数是2，2<50的开根号
再比如：15，最小质因数是3，3<15的开根号
合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数，则它是质数。
上面的定理是说，如果一个数能被它的最小质因数整除的话，那它肯定是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开跟后后的所有数整除，这样做的运算就会少了很多，因此效率也高了很多。
对应代码是：
只需要将之前的质数判断更改一下就可以了
///
///判断输入的数字是否是质数///
///
///
public static bool IsPrime(intn)
{bool flag = true;if (n < 2)
{throw newArgumentOutOfRangeException();
}int max =Convert.ToInt32(Math.Floor(Math.Sqrt(n)));for (int i = 2; i <= max; i++)
{if (n % i == 0)
{
flag= false;break;
}
}returnflag;
}
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(intn)
{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();
}
}
}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！