黑马程序员技术交流社区
标题:
如何判断素数
[打印本页]
作者:
张锟-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 编辑
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace test9
{
//9、 在label控件中随机输入20个1~1000之间的整数,求出其中所有的素数的和。
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
ArrayList arrList = new ArrayList();
private void button1_Click(object sender, EventArgs e)
{
int sum = 0;
//遍历数组
for (int i = 0; i < arrList.Count; i++)
{
//素数:除了1和自身没有可以整除的数
//检查一个正整数N是否为素数,最简单的方法就是试除法
//将该数N用小于等于根号N的所有素数去试除,若均无法整除,则N为素数
for (int j = 2; j < Math.Sqrt(Convert.ToInt32(arrList[i])); j++)
{
//遍历所有可能的数能否被整除
if (Convert.ToInt32(arrList[i]) % j == 0)
{
//能就踢出数组
arrList.Remove(arrList[i]);
//能被整除,跳出节省无用的运算
break;
}
}
}
//遍历求和
for (int i = 0; i < arrList.Count; i++)
{
sum += Convert.ToInt32(arrList[i]);
}
label2.Text += sum.ToString();
}
private void Form1_Load(object sender, EventArgs e)
{
//20个0-1000的数
Random ran = new Random();
for (int i = 0; i < 20; i++)
{
int num = ran.Next(0, 1000);
arrList.Add(num);
label1.Text += num + " ";
}
}
}
}
//我写的,希望对你有帮助
复制代码
作者:
张锟-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进行挨个求余,如果可除尽就不是素数跳出循环。上代码:
/// <summary>
/// 判断一个数是不是素数
/// </summary>
/// <param name="number">要判断的数字</param>
/// <returns>是素数或者不是素数</returns>
public static bool IsPrime(int number)
{
if (number < 2)//小于2的直接过滤掉
{
return false;
}
for (int i = 2; i <= number-1; i++)
{
if(number%i==0)//能被整除肯定就不是素数
{
return false;
}
}
return true;
}
复制代码
作者:
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