暴力枚举+埃氏筛+插入排序
2025-06-16 08:19:14
发布于：北京
1阅读
0回复
0点赞
暴力枚举，俗称枚举，穷举等。
枚举说白了就是循环，循环遍历来找出某个特定的元素
比如水仙花数：
#include <bits/stdc++.h>
using namespace std;
int main() {
for(int i=100;i<=999;i++){
if(pow(i%10,3)+pow(i/10%10,3)+pow(i/100,3)==i){
cout<<i<<endl;
}
}
return 0;
}
当你要在1~N之间找出所有的素数时......
你就会发现会TLE。这时就需要埃氏筛。
埃氏筛原理：要得到自然数n以内的全部素数，必须把不大于 根号n 的所有素数的倍数剔除，剩下的就是素数。
方法：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......
具体样例代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin>>n;
int a[n+1]={0};
a[1]=1;
for(int i=1;i<=n;i++){
if(a[i]==0){
for(int j=2*i;j<=n;j+=i){
a[j]=1;
}
}
}
int cnt=0;
for(int i=2;i<=n;i++){
if(a[i]==0)cnt++;
}
cout<<cnt;
return 0;
}
插入排序
我们现在有这样一道题：
输入 n (0<n≤100)，然后输入 n 个整数，将这 n 个数进行升序排列（使用插入排序），输出每一趟插入排序的结果。
样例组输入#1
5
6 5 1 3 2
样例组输出#1
5 6 1 3 2
1 5 6 3 2
1 3 5 6 2
1 2 3 5 6
我们可以用这个样例来讲一下插入排序的运算过程
对比6和5，5小于6，将5插入到6前面
对比6和1，对比5和1，发现1都小于他们，将1插入5前面
对比6和3，5和3，3都小于他们，但是3大于1，所以将3插入到5前面
对比6和2，5和2，3和2，他们都小于2，2大于1，将2插入3之前
具体代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int a[105];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<=n;i++){
int x=a[i];
int j=i-1;
while(j>=1&&a[j]>x){
a[j+1]=a[j];
j--;
}
a[j+1]=x;
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个