黑马程序员技术交流社区

标题: 如何判断素数 [打印本页]
作者: 张锟-i    时间: 2013-10-22 20:40
标题: 如何判断素数
本帖最后由 张锟-i 于 2013-10-22 22:00 编辑

我做的题是：随机20个1~1000之间的整数，求出其中所有的素数的和。
我的思路是：
1 、for循环20次 Random 随机出 20个1~1000的整数，并把每次的随机数添加到List中
2、在遍历List，判断素数，并相加；
可是素数老是想不出好点方法，求指导。
作者: Liu阳    时间: 2013-10-22 20:43
本帖最后由 Liu阳 于 2013-10-22 20:44 编辑
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.ComponentModel;
  5. using System.Data;
  6. using System.Drawing;
  7. using System.Linq;
  8. using System.Text;
  9. using System.Threading.Tasks;
  10. using System.Windows.Forms;

  12. namespace test9
  13. {
  14.     //9、 在label控件中随机输入20个1~1000之间的整数，求出其中所有的素数的和。

  16.     public partial class Form1 : Form
  17.     {
  18.         public Form1()
  19.         {
  20.             InitializeComponent();

  22.         }
  23.         ArrayList arrList = new ArrayList();
  24.         private void button1_Click(object sender, EventArgs e)
  25.         {
  26.             int sum = 0;
  27.             //遍历数组
  28.             for (int i = 0; i < arrList.Count; i++)
  29.             {
  30.                 //素数：除了1和自身没有可以整除的数
  31.                 //检查一个正整数N是否为素数，最简单的方法就是试除法
  32.                 //将该数N用小于等于根号N的所有素数去试除，若均无法整除，则N为素数
  33.                 for (int j = 2; j < Math.Sqrt(Convert.ToInt32(arrList[i])); j++)
  34.                 {
  35.                     //遍历所有可能的数能否被整除
  36.                     if (Convert.ToInt32(arrList[i]) % j == 0)
  37.                     {
  38.                         //能就踢出数组
  39.                         arrList.Remove(arrList[i]);
  40.                         //能被整除，跳出节省无用的运算
  41.                         break;
  42.                     }
  43.                 }
  44.             }
  45.             //遍历求和
  46.             for (int i = 0; i < arrList.Count; i++)
  47.             {
  48.                 sum += Convert.ToInt32(arrList[i]);
  49.             }
  50.             label2.Text += sum.ToString();
  51.         }

  53.         private void Form1_Load(object sender, EventArgs e)
  54.         {
  55.             //20个0-1000的数
  56.             Random ran = new Random();
  57.             for (int i = 0; i < 20; i++)
  58.             {
  59.                 int num = ran.Next(0, 1000);
  60.                 arrList.Add(num);
  61.                 label1.Text += num + " ";
  62.             }
  63.         }
  64.     }
  65. }
  66. //我写的，希望对你有帮助
复制代码
作者: 张锟-i    时间: 2013-10-22 21:47
Liu阳 发表于 2013-10-22 20:43

for (int i = 0; i < arrList.Count; i++)
            {
                //素数：除了1和自身没有可以整除的数
                //检查一个正整数N是否为素数，最简单的方法就是试除法
                //将该数N用小于等于根号N的所有素数去试除，若均无法整除，则N为素数
                for (int j = 2; j < Math.Sqrt(Convert.ToInt32(arrList)); j++)
                {
                    //遍历所有可能的数能否被整除
                    if (Convert.ToInt32(arrList) % j == 0)
                    {
                        //能就踢出数组
                        arrList.Remove(arrList);
                        //能被整除，跳出节省无用的运算
                        break;
                    }
                }
            }
这样不能把所有的元素都判断一边，arraylist中的元素每次都在减少，而i在逐渐增加，就会造成漏掉一部分非素数的数字。应该把不是素数的数字替换成0，这样才正确。
作者: 喜之郎果冻    时间: 2013-10-22 22:17
怎么判断素数呢？0和1不是素数，所以素数是从2开始的。素数的特点是只能被1和本身整除。所以我们可以让这个数跟2~它本身-1进行挨个求余，如果可除尽就不是素数跳出循环。上代码：
  1.    /// <summary>
  2.         /// 判断一个数是不是素数
  3.         /// </summary>
  4.         /// <param name="number">要判断的数字</param>
  5.         /// <returns>是素数或者不是素数</returns>
  6.         public static bool IsPrime(int number)
  7.         {
  8.             if (number < 2)//小于2的直接过滤掉
  9.             {
  10.                 return false;
  11.             }
  12.             for (int i = 2; i <= number-1; i++)
  13.             {
  14.                 if(number%i==0)//能被整除肯定就不是素数
  15.                 {
  16.                     return false;
  17.                 }
  18.             }
  19.             return true;

  21.         }
复制代码
作者: qdwyuotg    时间: 2013-10-23 08:39
素数即只能被1和其本身整除的数，判断n是否为素数只需用2~n/2或2~之间的数去除就可以了，常用2~n/2，因为一个数的一半的平方大于其本身是从5开始的。
如 :
            //定义一个int变量，用于存放求和数据
            int sum=0;
            //循环读取数组中的数据
            for (int i = 0; i < nums.Length; i++)
            {
                //定义一个标识变量
                bool isRight = false;
                //设置一个除数变量j并初始化为2
                for (int j = 2; j <nums[i]/2; j++)
                {
                    //素数判定：在2~n/2范围内没有一个自然数能够整除n.
                    //判断取舍是否为素数并为标志变量赋值
                    isRight = nums[i] % j == 0;
                    if (isRight)
                    {
                        //取值不是素数
                        break;
                    }
                }
                if (!isRight)
                {
                    //取值是素数时，累加求和，并将素数打印输出
                    sum += nums[i];
                    this.Text += nums[i].ToString()+" ";
                }               
            }



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2