http://blog.sina.com.cn/s/blog_622e77cc0100n5lm.html
1、根据质数的定义求
质数定义:只能被1或者自身整除的自然数(不包括1),称为质数。
利用它的定义可以循环判断该数除以比它小的每个自然数(大于1),如果有能被它整除的,则它就不是质数。
对应代码是:
/// <summary>/// 输出从2到max的所有质数/// </summary>/// <param name="max"></param>public static void Prime(int max){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();}}}}/// <summary>/// 判断输入的数字是否是质数/// </summary>/// <param name="n"></param>/// <returns></returns>public static bool IsPrime(int n){bool flag = true;if (n < 2){throw new ArgumentOutOfRangeException();}for (int i = 2; i <= n - 1; i++){if (n % i == 0){flag = false;break;}}return flag;}
求质数的公式?
2、利用一个定理——如果一个数是合数,那么它的最小质因数肯定小于等于他的平方根。例如:50,最小质因数是2,2<50的开根号
再比如:15,最小质因数是3,3<15的开根号
合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数,则它是质数。
上面的定理是说,如果一个数能被它的最小质因数整除的话,那它肯定是合数,即不是质数。所以判断一个数是否是质数,只需判断它是否能被小于它开跟后后的所有数整除,这样做的运算就会少了很多,因此效率也高了很多。
对应代码是:
只需要将之前的质数判断更改一下就可以了
/// <summary>/// 判断输入的数字是否是质数/// </summary>/// <param name="n"></param>/// <returns></returns>public static bool IsPrime(int n){bool flag = true;if (n < 2){throw new ArgumentOutOfRangeException();}int max = Convert.ToInt32(Math.Floor(Math.Sqrt(n)));for (int i = 2; i <= max; i++){if (n % i == 0){flag = false;break;}}return flag;}
求1~100之间的所有素数之和?3、筛法求质数,效率最高,但会比较浪费内存
首先建立一个boolean类型的数组,用来存储你要判断某个范围内自然数中的质数,例如,你要输出小于200的质数,你需要建立一个大小为201(建立201个存储位置是为了让数组位置与其大小相同)的boolean数组,初始化为true。
其次用第二种方法求的第一个质数(在此是2),然后将是2的倍数的数全置为false(2除外),即2、4、6、8……位置上置为false。然后是3的倍数的全置为false(3除外),一直到14(14是200的开平方),这样的话把不是质数的位置上置为false了,剩下的全是质数了,挑着是true的打印出来就行了。
对应代码是:
/// <summary>/// 输出从2到n的所有质数/// </summary>/// <param name="n"></param>public static void Prime(int n){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();}}}}