欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

确定性素性测试思想之Eratosthenes筛选法

程序员文章站 2024-03-21 15:32:10
...

素数:如果n (n > 1) 是素数, 当且仅当n只有因子1和它本身 ;


应⽤于:

数学: 自然数可由全体素数基底表达 

密码学: 构建基于RSA和椭圆曲线的公钥密码学内核 

一般方法: 判断n是否被i整除 (i = 2, 3,…, n1/2) ➡ 如果j > n1/2是n的因⼦子, 总能找到i < n1/2, 满⾜足n = i * j 

已知的判断素数的检测方法中的次数可达到sqrt(n),为进一步减少判断次数,引入一种确定性素性测试思想,删减{2, 3,…, n1/2}可能存在合数,减少合数重复判断Eratosthenes筛选。


实验原理:

(1)确定待筛选集合{2, 3,…, n1/2};

(2)基于{2, 3,…, n1/2}的Eratosthenes筛选;(从而开始递增的素数的倍数被标记为0)

(3)筛选后元素与n的整除判断n

 

代码实现:

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
	
	int a, i;
	cin >> a;
	int b[10000] = { 0 };//初始化为0,用于记录的数组
	int c = 0;//count计数

	for (int i = 2; i <= sqrt(a); i++)
	{
		b[i] = i;//从2到根号a依顺序给数组赋值
	}

	for (int i = 2; i <= sqrt(a); i++)
	{
		if (b[i] == 0)
			continue;//但凡因是倍数被赋0的都跳过
		for (int j = i + 1; j <= sqrt(a); j++)
		{
			if (b[j] % i == 0 && b[j] != 0)
			{
				b[j] = 0;//依次给凡是i的倍数赋值为0
			}
		}
		c++;
		b[c] = i;//初始化数组b,记录下符合条件的基数(素数)i
	}
	for (i = 1; i <= c; i++)
	{
		if (a%b[i] == 0)
		{
			cout << a << "不是素数!";
			break;
		}
	}
	if (i > c)
	{
		cout <<a<< "是素数!";
	}
}


VS2015编译环境运行结果:

确定性素性测试思想之Eratosthenes筛选法