999免费的网站,商务网站建设与维护 ppt,郑州软件开发外包,如何让网站 被百度kHalo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 现已更新完KMP算法、排序模板#xff0c;之… Halo这里是Ppeua。平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。 个人主页主页链接 算法专栏专栏链接 现已更新完KMP算法、排序模板之后我会继续往里填充内容哒。 LeetCode专栏专栏链接 目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出 代码仓库Gitee链接 点击关注收获更多优质内容 用一篇Blog来讲解下最近学到的数论为日后的刷题打下坚实的基础。
目录
试除法判断质数
朴素做法
代码模板:
改进做法 代码模板:
分解质因数 代码模板:
筛质数 埃式筛法:
欧拉筛(线性筛):
完结撒花 什么是质数 一个大于1的自然数除了1和它自身外不能被其他自然数整除的数 试除法判断质数
朴素做法
将定义进行模拟若整除了除1与其自身的另外的数则为质数
代码模板:
#includeiostream
using namespace std;
int n;
void prime(int x)
{if(x2){coutNoendl;return;}for(int i2;ix;i){if(x%i0){coutNoendl;return ;}}coutYesendl;return;
}
int main()
{cinn;while(n--){int x;cinx;prime(x);}
}
改进做法
一个数的两个因数都是成对出现的例如6的因数为 1 2 3 6
这里的2与3是成对出现的。所以我们无需从2-x的范围去遍历因为若前半部分没有出现则后半部分必然没有其因数
通过反证法若后半部分有其因数则就会出现这两个因数相乘会大于其本身。
所以应该满足 i*ix的范围,但又因为i*i在数字极大的情况下,很容易溢出,所以改成ix/i 代码模板:
#includeiostream
using namespace std;
int n;
void prime(int x)
{if(x2){coutNoendl;return;}for(int i2;ix/i;i){if(x%i0){coutNoendl;return ;}}coutYesendl;return;
}
int main()
{cinn;while(n--){int x;cinx;prime(x);}
}
分解质因数 与上文相同,依然是用到了i*in的这个性质,需要注意一下,最多存在一个sqrt(n)的质因子,同样可以用反证法来证明,这里就不过多赘述.所以当最后跳出循环时若还存在x1,也就是没有被模掉的情况时,则认为x为其较大的那个因子,也需要放进去.
若一个数能整除i,则i是其一个因子,又因为我们从小到达进行遍历,被整除的这个i必然为质因子,因为若为普通因子,在循环整除的时候已经被消掉了,化为其指数. 代码模板:
#includeiostream
using namespace std;
void divide(int x)
{for(int i2;ix/i;i)if(x%i0){int s0;while(x%i0){x/i;s;}printf(%d %d\n,i,s);}if(x1)printf(%d %d\n,x,1);puts();return ;
}
int main()
{int n0;cinn;while(n--){int x;cinx;divide(x);}return 0;
}
筛质数 埃式筛法:
一个约数其必然可以由数相乘得到.
假设有如下2到10的数
埃式筛法的核心就是:从头遍历每个数字,将其与每一个小于本身它本身的质数相乘,再将之后的数标记为非质数
也就是这样 可以看出 这里的质数就为2 3 5 7,
但我们很快就会发现,这个算法有一个弊端,假设这里的范围到12,就会出现当4*3的时候把十二标记为false了,但6*2又会将其标记一次,十分的不优雅.
所以就提出了另一个改进的算法
欧拉筛(线性筛):
当发现相乘的这个质数为其最小质因子时,则停止遍历
#includeiostream
using namespace std;
const int N1e69;
bool st[N];
int prime[N];
int main()
{int n0;int cnt0;cinn;for(int i2;in;i){if(!st[i]){prime[cnt]i;}for(int j0;prime[j]n/i;j){st[prime[j]*i]true;if(i%prime[j]0)break;}}coutcnt;
}
完结撒花 本篇博客的内容【数论:试除法判断质数分解质因数筛质数】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
