c">color:#1a439c;">目录

c" style="margin-left:0px;">ǹca;ǹca;ǹca;3.5 素数判定

c" style="margin-left:40px;">🥥例题：DreamJudge 1013

c" style="margin-left:40px;">🥥练习题目：

c" style="margin-left:80px;">DreamJudge 1355 素数判定 - 哈尔滨工业大学

c" style="margin-left:0px;">ǹca;ǹca;ǹca;3.6 素数筛选（🌷记模板）

c" style="margin-left:40px;">🥥例题：DreamJudge 1102

c" style="margin-left:40px;">🥥练习题目：

c" style="margin-left:80px;">DreamJudge 1375 素数

c" style="margin-left:0px;">ǹca;ǹca;ǹca;3.7 分解素因数

c" style="margin-left:40px;">🥥例题：DreamJudge 1156

c" style="margin-left:40px;">🥥练习题目：

c" style="margin-left:80px;">DreamJudge 1284 整除问题 🍰

c" style="margin-left:80px;">DreamJudge 1464 最大素因子

ǹca;ǹca;ǹca;3.5 素数判定

先说什么是素数？color:#ff9900;">素数就是其因子只有1和本身。

color:#494949;">那么如何判断一个数x是不是素数呢？我们可以根据素数的定义从2到小于这个数x的每个数去判断当前数是否为x的因子࿰c;也就是说࿰c;如果x有除了1和本身以外的因子࿰c;那他就不是素数。

color:#494949;">一般情况下࿰c;我们没有必要判断这么多个数࿰c;color:#ff9900;">只用判断到sqrt(x)就停止了color:#494949;">。这是因为࿰c;如果比 sqrt(x)大的数是其因子的话࿰c;就必然存在一个比sqrt(x)小的数是其因子。

🥥例题：DreamJudge 1013

class="img-center">c="https://i-blog.csdnimg.cn/direct/ed3a43e0985e4d049d68fae3fbabc704.png" width="500" />

color:#494949;">首先判断输入的 n 是不是一个素数࿰c;如果是的话就直接输出。如果不是的话࿰c;从 n+1 开始࿰c;对每个数去判断它是不是一个素数࿰c;直到找到一个素数的时候终止。

<code class="language-cpp">#include <stdio.h>
#include <math.h>
int main() {int n;scanf("%d", &n);if (n == 1) n++;//1 不是素数for (int i = n; ; i++) {int flag = 0;for (int j = 2; j <= sqrt(i); j++) {if (i % j == 0) {//如果找到了约数flag = 1;//说明不是素数break;}}if (flag == 0) {printf("%d\n", i);break;}}return 0;
}code>

color:#511b78;">🥥练习题目：

color:#333333;">ckground-color:#dad5e9;">DreamJudge 1355 素数判定 - 哈尔滨工业大学

c="https://i-blog.csdnimg.cn/direct/2f6151472ad14207b820cf3edc10da89.png" width="330" />c="https://i-blog.csdnimg.cn/direct/6f59f1b2908d424cb022045f816acd98.png" width="330" />

<code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
bool sushu(long long x)
{if(x==0||x==1||x<0) return false;for(long long i=2;i<x;i++) {if(x%i==0) return false;}return true;
}
int main()
{long long n;while(cin>>n){if(sushu(n)) cout<<"yes"<<endl;else cout<<"no"<<endl;}return 0;
}code>

ǹca;ǹca;ǹca;3.6 素数筛选（🌷记模板）

color:#494949;">有时࿰c;题目要求我们筛选出一段区间内的素数࿰c;我们就需要掌握一种素数筛选的方法。

color:#494949;">如果用上一节素数判定的方法去判定每一个数是不是素数的话࿰c;复杂度是 O(n*sqrt(n))࿰c;大概只能处理到 1e4 以内的数࿰c;color:#494949;">如果题目要求的范围大࿰c;我们就需要一种更为高效的筛选法。

color:#494949;">掌握下面这一种color:#ff9900;">线性复杂度的筛选方法color:#494949;">就足够我们应对任何情况：

<code class="language-cpp">// 线性素数筛选 prime[0]存的是素数的个数
const int maxn = 1e6 + 5;
int prime[maxn]={0};
void getPrime() {for (int i = 2; i <= maxn; i++) {if (!prime[i]) prime[++prime[0]] = i;for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {prime[prime[j] * i] = 1;if (i % prime[j] == 0) break;}}
}code>

🥥例题：DreamJudge 1102

class="img-center">c="https://i-blog.csdnimg.cn/direct/050dd6cb99dc4aa5acf5470d3faec6c8.png" width="500" />

class="img-center">c="https://i-blog.csdnimg.cn/direct/55fc2586170b48c48b518374d7f77ad7.png" width="500" />

color:#494949;">这道题的数据范围不大࿰c;可以用挨个暴力判断的方法解决。我们假设这道题的数据范围很大࿰c;使用素数筛选的方法来解决这个问题。

🥥练习题目：

color:#494949;">ckground-color:#dad5e9;">DreamJudge 1375 素数

c="https://i-blog.csdnimg.cn/direct/dd75dd03663b488a9ff5fe8aed508c23.png" width="330" />c="https://i-blog.csdnimg.cn/direct/ea71acfd33bf4a06a283160857a5f44a.png" width="330" />

<code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
bool prime(int x)
{if(x==1||x==0||x<0) return false;for(int i=2;i<x;i++){if(x%i==0) return false;}return true;
}int main()
{int n,flag=0;while(cin>>n){flag=0;for(int i=2;i<n;i++){if(prime(i)){if(i%10==1) {cout<<i<<" ";flag=1;}}}if(flag==0) cout<<-1;cout<<endl;}return 0;
}code>

ǹca;ǹca;ǹca;3.7 分解素因数

color:#494949;">对于任意一个大于1的整数࿰c;我们都可以把它分解成多个质因子相乘的形式。

color:#494949;">🥥例题：DreamJudge 1156

class="img-center">c="https://i-blog.csdnimg.cn/direct/1a4aa8e4e3bd40a6b4e3ae7d0839951d.png" width="500" />

color:#494949;">这道题目࿰c;我们可以用上一节学的素数筛选࿰c;先将所有的素数筛选出来。然后再不断的分解素数࿰c;直到将数分解到 1 为止。由于我们的素数筛选只能到 1000000࿰c;对于更大的素因子color:#494949;">我们可以不继续分解࿰c;因为不会存在两个大于 1000000 的素因子࿰c;如果存在࿰c;那么这个数的范color:#494949;">围一定大于题目所给的范围 10^9。

<code class="language-cpp">#include <bits/stdc++.h>
using namespace std;
// 线性素数筛选 prime[0]存的是素数的个数
const int maxn = 1000000 + 5;
int prime[maxn];
void getPrime() {memset(prime, 0, sizeof(prime));for (int i = 2; i <= maxn; i++) {if (!prime[i]) prime[++prime[0]] = i;for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {prime[prime[j] * i] = 1;if (i % prime[j] == 0) break;}}
}
int main() {getPrime();//先进行素数筛选预处理int n;while (scanf("%d", &n) != EOF) {int ans = 0;for (int i = 1; i <= prime[0]; i++) {while (n % prime[i] == 0) {//while就是为了解决重复因子的情况n /= prime[i];ans++;}}if (n > 1) ans++;printf("%d\n", ans);}return 0;
}code>

color:#511b78;">🥥练习题目：

color:#494949;">ckground-color:#dad5e9;">DreamJudge 1284 整除问题 🍰

c="https://i-blog.csdnimg.cn/direct/3fdc881cf4314358bdd71dbe2d8a11b5.png" width="330" />c="https://i-blog.csdnimg.cn/direct/0243fe0e34174b689e3513f7c2d1c7d3.png" width="330" />

<code class="language-cpp">//题解摘自N诺评论区用户：可以吖
#include<bits/stdc++.h>
using namespace std;
//getPrime就是统计质因子个数的。
void getPrime(vector<int>& factors, int n){for(int i=2; i*i<=n; i++){while(n % i == 0){factors[i]++;//相当于用数组计数࿰c;因为题中范围不大࿰c;所以可以直接开辟一个1000的数组。//并不是所有位置都用࿰c;只有成为n以及后面n--的质因子的位置才用。确实是稍微浪费了一些空间。n /= i;//这一步就是为了知道该数字有多少了等于i的质因子。比如单独考虑࿰c;12=2*2*3࿰c;里面有两个2࿰c;一个3。//则这一步以后factors[2]==2,factors[3]==1。if(n <= 1) return;}}if(n > 1) factors[n]++;//自身是一个。
}int main()
{int n,a;while(cin>>n>>a){vector<int> factor_a(1000), factor_n(1000);getPrime(factor_a,a);for(int i=2;i<=n;i++)getPrime(factor_n,i);//在i的质因子统计完以后࿰c;factor的已经存了个数࿰c;后续也是在这个基础上加int k=1000;for(int i=2;i<=a;i++)//为什么小于a࿰c;上述文字已经说明{if(factor_a[i])k=min(k,factor_n[i]/factor_a[i]);//注意前文定义k为int型。}cout<<k<<endl;}return 0;
}
code>

color:#494949;">ckground-color:#dad5e9;">DreamJudge 1464 最大素因子

 c="https://i-blog.csdnimg.cn/direct/82700fc0c14d48cdab1f6e4bed04c659.png" width="340" />c="https://i-blog.csdnimg.cn/direct/a3dc6ef8757f4995b092a742d6569ee4.png" width="330" />

<code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
bool isprime(int x)
{if(x==1||x==0||x<0) return false;for(int i=2;i<=sqrt(x);i++){if(x%i==0) return false;}return true;
}
int main()
{int n;while(cin>>n){string s;for(int i=0;i<n;i++){cin>>s;string cur="";for(int j=0;j<s.size();j++){if(s[j]>='0'&&s[j]<='9') cur+=s[j];}int num=0;for(int j=0;j<cur.size();j++) num=num*10+(cur[j]-'0');//cout<<cur<<" "<<num<<endl;//if(cur.size()==0||num==0) {//cout<<"yes3"<<endl;//cout<<0<<endl;continue;}if(isprime(num)) {//cout<<"yes"<<endl;//cout<<num<<endl;continue;}//cout<<num<<endl;//for(int j=num-1;j>=2;j--) {if(num%j==0){//cout<<j<<" yes2"<<endl;//cout<<j<<endl;break;}}}}return 0;
}code>

ckground-color:#f9eda6;">创作不易࿰c;点个赞吧~点赞收藏不迷路࿰c;感兴趣的宝子们欢迎关注该专栏~

ckground-color:#fbd4d0;">勤奋努力的宝子们࿰c;学习辛苦了！🌷🌷🌷休息下࿰c;我们下部分再见👋( •̀ ω •́ )✧~