5 Eulid扩展算法
5.1算法原理
如果整数a和b不都为0，那么存在整数x和y满足ax?by?gcd(a,b)
如果gcd(a,b)?1，则b在模a下有乘法逆元，即存在一个x 满足bx?1 (mod a) 用扩展欧几里得算法先求出gcd(a , b)，当gcd(a , b)?1时，则返回的y值就是b的乘法逆元。
5.2实现过程 5.2.1程序代码
using System;
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 mimaxue46.FormsClass {
public partial class ExtendEliud : Form {
public ExtendEliud() {
InitializeComponent(); }
private void button1_Click(object sender, EventArgs e) {
try {
int a = Convert.ToInt32(textBox1.Text); int b = Convert.ToInt32(textBox2.Text); int x = 1; int y = 0; int s = 1; int r = 0; int g = a; int t = b;
int q, u, v, w;
if (a >= b && b > 0) {
while (t > 0) {
q = g / t;
u = x - q * r; v = y - q * s; w = g - q * t; x = r; y = s; g = t; r = u; s = v; t = w; }
textBox3.Text = Convert.ToString(g); textBox4.Text = Convert.ToString(x); textBox5.Text = Convert.ToString(y); } else {
MessageBox.Show(\请保证a>=b>0\);
20
} } catch {
MessageBox.Show(\请输入正确格式的数字\); }
} } }
5.2.2运行界面
21
6 素性检验
6.1算法原理
素数的定义，当一个数只能被1 和自身整除时，这个数是素数。
古希腊数学家Eratosthenes(公元前276~公元前195)发现了一种找出不超过一个给定正整数的所有素数的方法，称为Eratosthenes筛法（Sieve of Eratosthenes）。所谓筛法就是将不合条件的整数筛掉，而将符合条件的整数“捉住”。Eratosthenes筛法筛选由大于1并且小于或等于n的所有自然数组成的数列。
首先取第一个素数2，划去所有除2以外的2的倍数。在余下的正整数中，大于刚刚取到的素数2的第一个正整数，即正整数3被认定为素数，其倍数(不包括自身)同样从数列中划去。这一过程持续到找到一个大于nn的素数为止
6.2实现过程 6.2.1程序代码
using System;
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 mimaxue46.FormsClass {
public partial class SuxingjianYan : Form {
22
public SuxingjianYan() {
InitializeComponent(); }
private void eulid(int n, int a) {
int r;
r = 1; a = n / 2;
while (r != 0) {
r = n % a; n = a; a = r; } }
private void button1_Click(object sender, EventArgs e) {
#region
int a = Convert.ToInt32(textBox1.Text); if (a == 1 || a == 2) {
label2.Text = \是素数\;
}
for (int i = 2; i < a; i++) {
if (a % i == 0) {
label2.Text = \不是素数\; break; } else {
label2.Text = \是素数\;
}
}
#endregion
} } }
23
6.2.2运行界面
24