目录
1.素数也叫质数
一个质数是一个大于1的自然数，只有两个正因数：1和它自身。这意味着如果一个数只有两个正因数，那么它就是一个质数。例如，2、3、5、7、11和13都是质数。
质数在数学和密码学中非常重要，因为它们具有一些独特的属性。例如，质数的乘积也是质数，如果一个数是两个质数的乘积，则这个数是质因数分解的唯一方式。这使得质数在密码学中非常有用，特别是在公钥加密中，例如RSA算法。
在编程中，可以使用不同的算法来检查一个数是否为质数，例如试除法、米勒-拉宾素性测试或AKS素性测试。
2. 试除法
试除法算法用于检查一个数字是否为质数。它通过尝试将2到a/2之间的所有数字除以a，并检查余数是否为0来工作。如果找到任何可以将a整除的数字，该函数返回false，表明a不是质数。如果在2到a/2之间的任何数字都不能将a整除，则该函数返回true，表明a是质数。
该算法不是特别高效，因为它检查了a的所有数字除数，但适用于小型数字。对于大型数字，更高效的算法，如米勒-拉宾素性测试或AKS素性测试，可能更合适。
//试除法判断素数
namespace _140_2
{
public partial class Form1 : Form
{
private GroupBox? groupBox1;
private TextBox? textBox1;
private Label? label1;
private Button? button1;
private Label? label2;
public Form1()
{
InitializeComponent();
StartPosition = FormStartPosition.CenterScreen;
Load += Form1_Load;
}
private void Form1_Load(object? sender, EventArgs e)
{
//
// textBox1
//
textBox1 = new TextBox
{
Location = new Point(84, 33),
Name = "textBox1",
Size = new Size(100, 23),
TabIndex = 1
};
//
// label1
//
label1 = new Label
{
AutoSize = true,
Location = new Point(18, 36),
Name = "label1",
Size = new Size(68, 17),
TabIndex = 0,
Text = "输入数字："
};
//
// groupBox1
//
groupBox1 = new GroupBox
{
Location = new Point(12, 12),
Name = "groupBox1",
Size = new Size(200, 85),
TabIndex = 0,
TabStop = false,
Text = "判断素数"
};
groupBox1.Controls.Add(textBox1);
groupBox1.Controls.Add(label1);
groupBox1.SuspendLayout();
//
// button1
//
button1 = new Button
{
Location = new Point(121, 103),
Name = "button1",
Size = new Size(75, 23),
TabIndex = 2,
Text = "判断",
UseVisualStyleBackColor = true
};
button1.Click += Button1_Click;
//
// label2
//
label2 = new Label
{
AutoSize = true,
Location = new Point(30, 109),
Name = "label2",
Size = new Size(43, 17),
TabIndex = 3,
Text = "label2"
};
//
// Form1
//
AutoScaleDimensions = new SizeF(7F, 17F);
AutoScaleMode = AutoScaleMode.Font;
ClientSize = new Size(224, 136);
Controls.Add(label2);
Controls.Add(button1);
Controls.Add(groupBox1);
Name = "Form1";
Text = "判断是否素数";
groupBox1.ResumeLayout(false);
groupBox1.PerformLayout();
}
private void Button1_Click(object? sender, EventArgs e)
{
int j = Convert.ToInt32(textBox1!.Text);
if (Prime(j) == true)
{
label2!.Text = "是素数";
}
else
{
label2!.Text = "不是素数";
}
}
/// <summary>
/// 试除法判断素数
/// </summary>
static bool Prime(int a)
{
int i;
if (a == 2)
return true;
//else if (a == 4) { return false; }
//如果使用上面这条语句，那么for循环条件用<；
//如果不用上面这条语句，那么for循环条件用<=；
//区别在于循环数量多一次
else
{
for (i = 2; i <= a / 2; i++)
{
if (a % i == 0)
return false;
}
return true;
}
}
}
}
3.优化的试除法_1
步骤2里的试除法将2到a/2之间的所有数字除以a。优化的试除法_1首先检查a是否为2，因为2是唯一的偶数质数。然后，如果a为1或偶数，该算法返回false，因为1和所有偶数（除了2）都不是质数。最后，如果a为奇数，则该算法执行试除法，仅检查3到a的平方根之间的奇数是否可以将a整除。这比原始算法更有效，因为它避免了检查2到a/2之间的所有数字。
//优化的试除法判断素数
namespace _140_1
{
public partial class Form1 : Form
{
private GroupBox? groupBox1;
private TextBox? textBox1;
private Label? label1;
private Button? button1;
private Label? label2;
public Form1()
{
InitializeComponent();
StartPosition = FormStartPosition.CenterScreen;
Load += Form1_Load;
}
private void Form1_Load(object? sender, EventArgs e)
{
//
// textBox1
//
textBox1 = new TextBox
{
Location = new Point(84, 33),
Name = "textBox1",
Size = new Size(100, 23),
TabIndex = 1
};
//
// label1
//
label1 = new Label
{
AutoSize = true,
Location = new Point(18, 36),
Name = "label1",
Size = new Size(68, 17),
TabIndex = 0,
Text = "输入数字："
};
//
// groupBox1
//
groupBox1 = new GroupBox
{
Location = new Point(12, 12),
Name = "groupBox1",
Size = new Size(200, 85),
TabIndex = 0,
TabStop = false,
Text = "判断素数"
};
groupBox1.Controls.Add(textBox1);
groupBox1.Controls.Add(label1);
groupBox1.SuspendLayout();
//
// button1
//
button1 = new Button
{
Location = new Point(121, 103),
Name = "button1",
Size = new Size(75, 23),
TabIndex = 2,
Text = "判断",
UseVisualStyleBackColor = true
};
button1.Click += Button1_Click;
//
// label2
//
label2 = new Label
{
AutoSize = true,
Location = new Point(30, 109),
Name = "label2",
Size = new Size(43, 17),
TabIndex = 3,
Text = "label2"
};
//
// Form1
//
AutoScaleDimensions = new SizeF(7F, 17F);
AutoScaleMode = AutoScaleMode.Font;
ClientSize = new Size(224, 136);
Controls.Add(label2);
Controls.Add(button1);
Controls.Add(groupBox1);
Name = "Form1";
Text = "判断是否素数";
groupBox1.ResumeLayout(false);
groupBox1.PerformLayout();
}
private void Button1_Click(object? sender, EventArgs e)
{
int j = Convert.ToInt32(textBox1!.Text);
if (Prime(j) == true)
{
label2!.Text = "是素数";
}
else
{
label2!.Text = "不是素数";
}
}
/// <summary>
/// 优化的试除法判断素数
/// </summary>
static bool Prime(int a)
{
int i;
if (a == 2)
return true;
else if (a == 1 || a % 2 == 0)
return false;
else
{
for (i = 3; i * i <= a; i += 2)
{
if (a % i == 0)
return false;
}
return true;
}
}
}
}
4.优化的试除法_2
步骤2里的试除法将2到a/2之间的所有数字除以a。优化的试除法_1在2到a/2的范围内筛除偶数。
优化的试除法_2是通过遍历从2到这个数的平方根之间的所有整数，检查这个数是否可以被这些整数整除。如果可以被任何一个整数整除，那么这个数就不是素数。否则，这个数就是素数。
//优化的试除法_2判断素数
namespace _140_3
{
public partial class Form1 : Form
{
private GroupBox? groupBox1;
private TextBox? textBox1;
private Label? label1;
private Button? button1;
private Label? label2;
public Form1()
{
InitializeComponent();
StartPosition = FormStartPosition.CenterScreen;
Load += Form1_Load;
}
private void Form1_Load(object? sender, EventArgs e)
{
//
// textBox1
//
textBox1 = new TextBox
{
Location = new Point(84, 33),
Name = "textBox1",
Size = new Size(100, 23),
TabIndex = 1
};
//
// label1
//
label1 = new Label
{
AutoSize = true,
Location = new Point(18, 36),
Name = "label1",
Size = new Size(68, 17),
TabIndex = 0,
Text = "输入数字："
};
//
// groupBox1
//
groupBox1 = new GroupBox
{
Location = new Point(12, 12),
Name = "groupBox1",
Size = new Size(200, 85),
TabIndex = 0,
TabStop = false,
Text = "判断素数"
};
groupBox1.Controls.Add(textBox1);
groupBox1.Controls.Add(label1);
groupBox1.SuspendLayout();
//
// button1
//
button1 = new Button
{
Location = new Point(121, 103),
Name = "button1",
Size = new Size(75, 23),
TabIndex = 2,
Text = "判断",
UseVisualStyleBackColor = true
};
button1.Click += Button1_Click;
//
// label2
//
label2 = new Label
{
AutoSize = true,
Location = new Point(30, 109),
Name = "label2",
Size = new Size(43, 17),
TabIndex = 3,
Text = "label2"
};
//
// Form1
//
AutoScaleDimensions = new SizeF(7F, 17F);
AutoScaleMode = AutoScaleMode.Font;
ClientSize = new Size(224, 136);
Controls.Add(label2);
Controls.Add(button1);
Controls.Add(groupBox1);
Name = "Form1";
Text = "判断是否素数";
groupBox1.ResumeLayout(false);
groupBox1.PerformLayout();
}
private void Button1_Click(object? sender, EventArgs e)
{
int j = Convert.ToInt32(textBox1!.Text);
if (Prime(j) == true)
{
label2!.Text = "是素数";
}
else
{
label2!.Text = "不是素数";
}
}
/// <summary>
/// 优化的试除法判断素数
/// </summary>
public static bool Prime(int number)
{
if (number <= 1)
{
return false;
}
for (int i = 2; i <= Math.Sqrt(number); i++)
{
if (number % i == 0)
{
return false;
}
}
return true;
}
}
}
5.优化的试除法_3
步骤2里的试除法将2到a/2之间的所有数字除以a。优化的试除法_1在2到a/2的范围内筛除偶数。优化的试除法_2是通过遍历从2到这个数的平方根之间的所有整数。
优化的试除法_3只检查从2到这个数的平方根之间的奇数是否可以整除这个数。因为任何大于1的自然数都可以表示为2的幂次方乘以一个奇数，所以只需要检查奇数是否可以整除这个数，这样可以减少一半的检查次数。
//优化的试除法_3判断素数
namespace _140_4
{
public partial class Form1 : Form
{
private GroupBox? groupBox1;
private TextBox? textBox1;
private Label? label1;
private Button? button1;
private Label? label2;
public Form1()
{
InitializeComponent();
StartPosition = FormStartPosition.CenterScreen;
Load += Form1_Load;
}
private void Form1_Load(object? sender, EventArgs e)
{
//
// textBox1
//
textBox1 = new TextBox
{
Location = new Point(84, 33),
Name = "textBox1",
Size = new Size(100, 23),
TabIndex = 1
};
//
// label1
//
label1 = new Label
{
AutoSize = true,
Location = new Point(18, 36),
Name = "label1",
Size = new Size(68, 17),
TabIndex = 0,
Text = "输入数字："
};
//
// groupBox1
//
groupBox1 = new GroupBox
{
Location = new Point(12, 12),
Name = "groupBox1",
Size = new Size(200, 85),
TabIndex = 0,
TabStop = false,
Text = "判断素数"
};
groupBox1.Controls.Add(textBox1);
groupBox1.Controls.Add(label1);
groupBox1.SuspendLayout();
//
// button1
//
button1 = new Button
{
Location = new Point(121, 103),
Name = "button1",
Size = new Size(75, 23),
TabIndex = 2,
Text = "判断",
UseVisualStyleBackColor = true
};
button1.Click += Button1_Click;
//
// label2
//
label2 = new Label
{
AutoSize = true,
Location = new Point(30, 109),
Name = "label2",
Size = new Size(43, 17),
TabIndex = 3,
Text = "label2"
};
//
// Form1
//
AutoScaleDimensions = new SizeF(7F, 17F);
AutoScaleMode = AutoScaleMode.Font;
ClientSize = new Size(224, 136);
Controls.Add(label2);
Controls.Add(button1);
Controls.Add(groupBox1);
Name = "Form1";
Text = "判断是否素数";
groupBox1.ResumeLayout(false);
groupBox1.PerformLayout();
}
private void Button1_Click(object? sender, EventArgs e)
{
int j = Convert.ToInt32(textBox1!.Text);
if (Prime(j) == true)
{
label2!.Text = "是素数";
}
else
{
label2!.Text = "不是素数";
}
}
/// <summary>
/// 优化的试除法判断素数
/// </summary>
public static bool Prime(int number)
{
if (number <= 1)
{
return false;
}
for (int i = 2; i <= Math.Floor(Math.Sqrt(number)); i += 2)
{
if (number % i == 0)
{
return false;
}
}
for (int i = 3; i <= Math.Floor(Math.Sqrt(number)); i += 2)
{
for (int j = i * i; j <= number; j += i)
{
if (number % j == 0)
{
return false;
}
}
}
return true;
}
}
}
6.米勒-拉宾素数检测算法
使用更高级的算法，如米勒-拉宾素数检测算法（Miller-Rabin Primality Test），这是一种概率算法，通过反复应用费马小定理来判断一个数是否为素数。
// 米勒-拉宾素数检测算法（Miller-Rabin Primality Test）判断素数
using System.Numerics;
namespace _140_5
{
public partial class Form1 : Form
{
private GroupBox? groupBox1;
private TextBox? textBox1;
private Label? label1;
private Button? button1;
private Label? label2;
public Form1()
{
InitializeComponent();
StartPosition = FormStartPosition.CenterScreen;
Load += Form1_Load;
}
private void Form1_Load(object? sender, EventArgs e)
{
//
// textBox1
//
textBox1 = new TextBox
{
Location = new Point(84, 33),
Name = "textBox1",
Size = new Size(100, 23),
TabIndex = 1
};
//
// label1
//
label1 = new Label
{
AutoSize = true,
Location = new Point(18, 36),
Name = "label1",
Size = new Size(68, 17),
TabIndex = 0,
Text = "输入数字："
};
//
// groupBox1
//
groupBox1 = new GroupBox
{
Location = new Point(12, 12),
Name = "groupBox1",
Size = new Size(200, 85),
TabIndex = 0,
TabStop = false,
Text = "判断素数"
};
groupBox1.Controls.Add(textBox1);
groupBox1.Controls.Add(label1);
groupBox1.SuspendLayout();
//
// button1
//
button1 = new Button
{
Location = new Point(121, 103),
Name = "button1",
Size = new Size(75, 23),
TabIndex = 2,
Text = "判断",
UseVisualStyleBackColor = true
};
button1.Click += Button1_Click;
//
// label2
//
label2 = new Label
{
AutoSize = true,
Location = new Point(30, 109),
Name = "label2",
Size = new Size(43, 17),
TabIndex = 3,
Text = "label2"
};
//
// Form1
//
AutoScaleDimensions = new SizeF(7F, 17F);
AutoScaleMode = AutoScaleMode.Font;
ClientSize = new Size(224, 136);
Controls.Add(label2);
Controls.Add(button1);
Controls.Add(groupBox1);
Name = "Form1";
Text = "判断是否素数";
groupBox1.ResumeLayout(false);
groupBox1.PerformLayout();
}
private void Button1_Click(object? sender, EventArgs e)
{
int j = Convert.ToInt32(textBox1!.Text);
if (Prime(j) == true)
{
label2!.Text = "是素数";
}
else
{
label2!.Text = "不是素数";
}
}
/// <summary>
/// 米勒-拉宾素数检测算法（Miller-Rabin Primality Test）判断素数
/// </summary>
public static bool Prime(int number)
{
if (number <= 1)
{
return false;
}
if (number == 2 || number == 3)
{
return true;
}
if (number % 2 == 0)
{
return false;
}
int s = 0;
int d = number - 1;
while (d % 2 == 0)
{
s++;
d /= 2;
}
Random rand = new();
int a = rand.Next(2, number - 1);
BigInteger x = BigInteger.ModPow(a, d, number);
if (x == 1 || x == number - 1)
{
return true;
}
for (int i = 0; i < s; i++)
{
x = BigInteger.ModPow(x, 2, number);
if (x == number - 1)
{
return true;
}
}
return false;
}
}
}
