最小质因数

2023-09-01 07:16| 来源: 网络整理| 查看: 265

在这里插入图片描述

观测输入组数和数字的大小普通的素数判断方法就显得力不从心了利用数学的性质，就可以很好的解决该问题

整体思路是抓奇数然后对奇数进行翻倍原理是：奇数的倍数一定不是质数所以每个奇数的倍数可以将每个非质数的数都赛选出来如果没有筛到的数那就一定是质数所以开头写一个循环让每个数等于自己的本身

//对奇数的倍数j进行筛出 // 那么i一定是j的因子 // 但是 3 9 都是18的因子 // 所以一定要保存最小的因子 // 题目要求的是质因子

问题来了，如何判定i是不是质数呢？（i是奇数）打个比方 i=9 or 21 的时候 (最开始的i）首先因为i不是质数 i一定有因子那么i的因子一定是奇数因为奇数*奇数才等于奇数所以 i的因子 k一定是奇数再假设k是非质数那么k的因子也还是奇数 … 以此循环直到因子为质数那么这个最终的因子的倍数一定可以筛出最开始i的倍数所以我们不需要考虑i是否是质数直接筛就完事了！ 18 27 的

#include #include using namespace std; const int N = 1e6; int isprime[1000005] = {}; int main() { for (int i = 1; i //对奇数的倍数j进行筛出 // 那么i一定是j的因子 // 但是 3 9 都是18的因子 // 所以一定要保存最小的因子 for (int j = i * 2; j isprime[j] = i; } } } int t; scanf("%d", &t); while (t--) { int x; scanf("%d", &x); if (x % 2 == 0)//偶数最小因子一定是2 { printf("2\n"); } else { printf("%d\n", isprime[x]); } } }

【本文地址】

最小质因数

最小质因数

今日新闻

推荐新闻