首页 > 编程语言 >【数论算法赌场】质数概念.判断和打表

【数论算法赌场】质数概念.判断和打表

时间:2024-11-03 11:16:53浏览次数:3  
标签:数论 合数 枚举 sqrt 因数 打表 质数

大家好我是#Y清墨,今天讲的是质数判断和打表。

一.质数的相关概念

质数的定义

除了 1 和自身,找不到其它因数的数。例如 7 和 13 都是质数。最小的质数是 2 。

合数

除了 1 和自身,能找到其它因数的数。例如 10,16 均是合数。最小和合数是 4 。

特殊情况

数字 1 既不是质数,也不是合数。这个特殊情况一定要牢记,在写程序的需要可能需要加一个特殊判断分支。

二.判断一个数是不是质数。

因为质数不可能包含 1 和自身以外的别的因数,所以,一个个数去枚举测试,如果找不到 1 和 自身以外的因数,就可以判断这个数位质数。

但是,上面这个办法很笨,如果遇到很大的质数那么枚举的次数是非常多的。实际上可以进一步优化: 只需要枚举从 2 到 sqrt(n) 即可,如果找不到因数就可以判断 n 是质数 

如果有 i 是 n 的因数,那么 n/i 也一定是 n 的因数。 i 和 n/i 两个数起码有一个数是小于等于 sqrt(n) 的。我们可以用反证法轻松的证明这一点。也就是说,如果一个数是合数,那么肯定找得到至少 1 个因数是小于等于它的平方根的,如果找不到,则可以推断出它就是质数。这一点小小的改进所带来的好处是巨大的。以 9999999979 为例,这是一个很大的质数,如果用笨方法,就要从 2 一直枚举到 9999999979 ,而优化之后,只需要从 2 枚举到 37550 ( sqrt(9999999979) 取整之后是 37550 ),9999999979 和 37550 相差了很多个数量级。

bool prime_check(int n)
{
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==2)
			return false;
	
	return true;
}

2.1暴力枚举分解质因数

枚举 2 到 n 之间的数,只要是 n 的因数就分解,分解的时候用 while 语句,因为有可能同一个因数包含了多个,例如 48 就包含了 4 个质因数 2。

因为是从小到大枚举的,所以,分解出来的因数一定数是从小到大,一定就是质因数了。例如分解 48 , 虽然 12 也是一个因数,但是因为枚举到 2 的时候就把所有的因数 2 分解掉了,枚举到 3 的时候又把所有的因数 3 分解掉了,因此不会分解出因数 12 。

	for(i=2;n>1;i++) //如果 n 变成 1 就不用分解了,这可以作为循环的退出条件 
	{
		while(n%i==0)
		{
			printf("%d ",i);
			n /= i;
		}			
	}

2.2对一个更大的数字分解质因数

当遇到一个很大的 n ,而且 n 是一个质数,那么上面的方法会一直从 2 枚举到 n,运算复杂度很大,很容易导致超时。还是可以利用质数判断的知识,我们只枚举到 sqrt(n),如果还没有能够把 n 分解成 1,那么我们就认为 n 是一个质数。所以,离开循环之后,要补充做一次判断。

	int nn = sqrt(n); // sqrt函数返回的是浮点数,赋值给 int 变量 nn 的时候做了强制转换,小数部分被截断 
	for(i=2;i<=nn;i++)
	{
		while(n%i==0)
		{
			printf("%d ",i);
			n /= i;
		}
		if(n==1) break; //有这句是可以更快一些,没有也问题不大 
	}

	if(n!=1) //说明了 n 是质数。对一个质数分解质因数就是输出它自己 
		printf("%d",n);

    2.3因数的个数

如果 i 是 n 的因数,说明了 i 能整除 n ,假设 n/i = j , 那意味着 j 也是 n 的因数。 所以, i 和 n/i 是 一对因数,知道一个就可以算出另外一个。

在某些情况下 i 和 n/i 是同一个数,例如当 n = 144 , i = 12 的时候 n/i=144/12=12 。只有当 n 是平方数的时候才会有这个情况。

有一些题目会让学生计算 n 的因数个数,用笨方法,就是从 1 枚举到 n ;通过上面的数学知识,我们可以改进一下:

  • 枚举 i ,从 1 枚举到 sqrt(n) , 如果 i 是 n 的因数,则答案增加 2
  • 最后,如果 n 是完全平方数,则总数减一
	int cnt = 0;
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==0)
			cnt += 2;

	int j = sqrt(n);
	if(j*j==n)
		cnt--;

三.质数打表

3.1为什么需要质数打表

我们已经学习了如何判断一个数是不是质数了,但是还不够。假设要判断很多很多个数是不是质数的时候,之前的学习的方法效率不够高。因为,如果 n 是质数,需要从 2 枚举到 sqrt(n) ,如果题目里面要你几百几千个数逐一判断是否是质数,则很可能会超时。

所谓 质数打表,是指先通过一段比较高效的代码,完成了前期运算,把每一个数是不是质数的信息 表格化 ,在程序的其它位置,如果需要判断一个数是不是质数,只需要去这个预先计算好的表格里面查一下就可以了。

3.2质数打表的算法思路

我们只需要把合数找到,那么自然就能找到质数了。而找合数的思路,则是:从小到大去找质数,每找到一个新的质数,则去把这个质数的倍数标记出来,这些倍数就是合数,而那些自始至终没有被标记过的数就是质数。例如,当我们指导 13 是质数的时候,我们就把 26,39,52,65... 等一系列的合数标记出来。

下面是质数打表的代码:

bool flag[1000001];
void prepare_prime() //质数打表的函数 
{
	int i,j;
	
	for(i=2;i<=1000000;i++)
	{
		if(!flag[i]) //表示 i是一个质数
		{
			for(j=2;i*j<=1000000;j++) //对 j 的倍数(不包含自己)全部设置标记,表示这些数是合数 
				flag[i*j] = true; 
		}
	}
}

执行了上面的 prepare_prime( ) 函数,就产生了 1000000 以内的质数表了。当 flag[i] 为true,表示 i 是合数,flag[i] 为 false 则表示 i 是质数。 1 是特殊的,1 既不是质数又不是合数,单独判断。

3.3常见错误

本来题目要你找出 n 以内的素数,但是你打表的时候的第一层循环只循环到 sqrt(n) ,这是错误的,这会漏掉了很多 比 sqrt(n) 大的质数。

标签:数论,合数,枚举,sqrt,因数,打表,质数
From: https://blog.csdn.net/dazys/article/details/143452829

相关文章

  • 基础数论
    基础数论Update:2024/11/02。素数素数和合数定义若\(p\in\Zeta\),且\(p\not=0,\pm1\),其约数集合中的元素只有\(1\)和\(p\)本身,那么称\(p\)为素数。若\(a\in\Zeta\),且\(a\not=0,\pm1\),\(a\)不为素数,则为合数。素数一般指正的素数。素数计数\(\pi(x)......
  • 数论
    质数唯一分解定理任意一个正整数都可以唯一地表示成若干个素数的乘积,其中素数因子从小到大依次出现(这里的“乘积”可以有0个、1个或多个素因子)。埃氏筛要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。时间复杂度\(O(nlogn)\)a[1]=1;......
  • 质数因子
    链接:质数因子_牛客题霸_牛客网描述:功能:输入一个正整数,按照从小到大的顺序输出它的所有质因子(重复的也要列举)(如180的质因子为2 2 3 3 5 ) 数据范围: 1≤n≤2×109+14 1≤n≤2×109+14 输入描述:输入一个整数输出描述:按照从小到大的顺序输出它的所有质数的因子......
  • C06.L01.筛选法求质数.质数个数(筛选法优化)
    题目描述输入n,输出1~n以内的质数的个数。(n<=1000)输入格式一个整数n。输出格式一个整数,代表1~n以内的质数的个数。样例输入数据110Copy输出数据14代码:#include<bits/stdc++.h>usingnamespacestd;boolflag[1001];intmain(){     ......
  • 数学数论专项练习 day 60
    linkA显然只需要考虑质因子。首先\(k\)只有一个质因子可以特判,有两个可以exgcd有三个及其以上那么最小的一个\(\le10^5\),同余最短路即可。B考虑一个序列$\lbracex|x=a_ib_i^t,t\in\mathbb{N}\rbrace$,对于一个质因子提出了怎样的限制?设\(a_i,b_i\)在质因数\(p\)......
  • [复习] 数论基础
    [复习]数论基础模运算\[(a\pmb)\bmodp=((a\bmodp)\pm(b\bmodp))\bmodp\]\[(a\timesb)\bmodp=((a\bmodp)\times(b\bmodp))\bmodp\]积性函数\[\forall\gcd(x,y)=1,f(xy)=f(x)\timesf(y)\]完全积性函数\[\forallx,y\inN^+,f(xy)=f(x)\timesf(y)\]g......
  • 快速幂已经快速幂求逆元(数论)
    快速幂模板给定 n 组 ai,bi,pi对于每组数据,求出 ai^bimodpi 的值。输入格式第一行包含整数 n。接下来 n 行,每行包含三个整数 ai,bi,pi。输出格式对于每组数据,输出一个结果,表示 ai^bimodpi 的值。每个结果占一行。数据范围1≤n≤1000001≤ai,bi,pi......
  • 素数的由来质数的由来
    素数的由来古希腊数学家的贡献:在古希腊,数学家们已经开始研究质数的性质和规律。欧几里得在《几何原本》中将这类特殊的数称为“素数”,其中“素”一词在古希腊语中的意思是“单纯的”、“纯粹的”,用以描述质数不可分解、具有纯粹数学性质的特性。中国古代数学的传承:在中国古代,数......
  • 【重拾算法第一天】质数&&约数&&欧拉筛 埃氏筛&&GCD
    1.素数素数(PrimeNumber)是指大于1的自然数,只有两个正因数:1和它自身。换句话说,素数是不能被其他自然数整除的数。1.1小素数的判定判定一个数是否为素数,当N≤  时,用试除法,当n>  时,用Miller_Rabin算法根据素数的定义,可以直接得到试除法,用[2,n-1]内的所有数着......
  • 一些有趣的数论题 - Updating
    P2568GCD给定正整数\(n\),求正整数数对\((x,y)\)的个数,该数对满足\(x\leqn,y\leqn\)且\(\gcd(x,y)\)是质数。首先我们可以枚举质数\(p\),求出\(\gcd(x,y)=p\)的数对个数然后对每一个质数求和即可。所以考虑如何求这个子问题。给定质数\(p\),求满足\(x\leqn,y\l......