蓝桥杯准备 【入门3】循环结构

素数小算法（埃氏筛&&欧拉筛）

以下四段代码都是求20以内的所有素数

1.0版求素数

#include<iostream>
using namespace std;int main() {int n = 20;for(int i=2;i<=n;i++){int j=0;for(j=2;j<=i;j++)//遍历i{if(i%j==0){break;}}if(i==j){cout<<i<<endl;}}return 0;
}

2.0版（最爱的一版）

任何合数是两个数相乘得的，很明显，其中一个数必小于等于sqrt（合数），所以我们在上一段代码的基础上，只遍历2-sqrt（该数）即可

#include<iostream>
using namespace std;int main() {int n = 20;for(int i=2;i<=n;i++){int j=0;for(j=2;j*j<=i;j++)//遍历一部分{if(i%j==0){break;}}if(j*j>i){cout<<i<<endl;}}return 0;
}

3.0版（埃氏筛）

就这样把质数的倍数，一点点false掉

#include<iostream>
using namespace std;
int main()
{int n=20;bool isprime[n+1];for(int i=0;i<n+1;i++){isprime[i]=true;}isprime[0]=false;isprime[1]=false;for(int i=2;i<n+1;i++){if(isprime[i]){for(int j=i*i;j<n+1;j+=i){isprime[j]=false;}	}	}for(int i=0;i<n+1;i++){if(isprime[i]){cout<<i<<endl;}}return 0;
}

4.0版（欧拉筛）

跟上一个埃氏筛，不会重复，也是一点点false掉筛去

#include<iostream>
using namespace std;int main() {int n = 20;bool isprime[n + 1];int primes[n + 1];  for (int i = 0; i <= n; i++) {isprime[i] = true;}isprime[0] = false;isprime[1] = false;int prime_count = 0;  for (int i = 2; i <= n; i++) {if (isprime[i]) {primes[prime_count] = i;  prime_count++;}for (int j = 0; j < prime_count && primes[j] <= n / i ; j++) {isprime[primes[j] * i] = false;if (i % primes[j] == 0) {break;}}}for (int i = 2; i <= n; i++) {if (isprime[i]) {cout << i << endl;}}return 0;
}

---

P5723 【深基4.例13】质数口袋

题目描述

小 A 有一个质数口袋，里面可以装各个质数。他从 22 开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。

口袋的负载量就是口袋里的所有数字之和。

但是口袋的承重量有限，装的质数的和不能超过 LL。给出 LL，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数的个数，数字之间用换行隔开。

代码

注意特殊点1和0

解法一

#include<iostream>
using namespace std;
int main(){int n;cin>>n;int sum=0;int prime[10000]={0};int c=0;for(int i=2;i<=100000;i++){int j=0;for(j=2;j*j<=i;j++){if(i%j==0){break;}}if(j*j>i){prime[c++]=i;}}int count=0;if(n>=2){for(int i=0;i<c-1;i++){cout<<prime[i]<<endl;sum+=prime[i];count++;if(sum+prime[i+1]>n){break;}}}cout<<count<<endl;
}

解法二

#埃氏筛
#include<iostream>
using namespace std;
int main(){int n;cin>>n;int sum=0;int prime[10000]={0};//储存素数bool isprime[100000];//判断素数for(int i=0;i<100000;i++)//全部置true{isprime[i]=true;}int c=0;isprime[0]=false;isprime[1]=false;//注意 0 1不是素数for(int i=2;i<=100000;i++)//开始筛选{if(isprime[i]){prime[c++]=i;for(long long j=(long long)i*i;j<100000;j+=i){isprime[j]=false;//合数置假}}}int count=0;//计数if(n>=2)//注意n等于0 1 时应该输出0{for(int i=0;i<c-1;i++){cout<<prime[i]<<endl;//输出sum+=prime[i];count++;if(sum+prime[i+1]>n){break;}}}cout<<count<<endl;//输出
}

解法三

#欧拉筛
#include<iostream>
using namespace std;
int main(){int n;cin>>n;int sum=0;int prime[10000]={0};bool isprime[100001];for(int i=0;i<=100000;i++){isprime[i]=true;}int c=0;isprime[0]=false;isprime[1]=false;for(int i=2;i<=100000;i++)//筛{if(isprime[i]){prime[c++]=i;}for(int j=0; j < c && prime[j] <= 100000 / i;j++){isprime[prime[j]*i]=false;if(i%prime[j]==0){break;}}}int count=0;if(n>=2){for(int i=0;i<c-1;i++){cout<<prime[i]<<endl;sum+=prime[i];count++;if(sum+prime[i+1]>n){break;}}}cout<<count<<endl;
}

P1217 [USACO1.5] 回文质数 Prime Palindromes

题目描述

因为 151151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151151 是回文质数。

写一个程序来找出范围 [a,b](5≤a<b≤100,000,000)[a,b](5≤a<b≤100,000,000)（一亿）间的所有回文质数。

代码

#include<iostream>
using namespace std;
int main(){int n,m;cin>>n>>m;int a[10]={0}; //数组储存每位数for(int i=n;i<=m;i++){bool hui=true;//注意在此位置初始化hui为trueint x=i;int c=0;while(x>0){a[c++]=x%10;x=x/10;}for(int j=0;j<=c/2;j++)//判断是否是回文数{if(a[j]!=a[c-j-1]){hui=false;break;}}if(hui)//在回文的条件下判断是否是质数{	int j=2;for(j=2;j*j<=i;j++){if(i%j==0){break;}}if(j*j>i){cout<<i<<endl;//输出}}}
}

P1423 小玉在游泳

题目描述

小玉开心的在游泳，可是她很快难过的发现，自己的力气不够，游泳好累哦。已知小玉第一步能游 22 米，可是随着越来越累，力气越来越小，她接下来的每一步都只能游出上一步距离的 98%98%。现在小玉想知道，如果要游到距离 ss 米的地方，她需要游多少步呢。请你编程解决这个问题。

代码

普通方法

（窝感觉是暴力解法，hhh）

 #include<iostream>using namespace std;int main(){double n;cin>>n;double s=2.0;double sum=2.0;if(n<=2)//特判{cout<<"1"<<endl;}else if(n>2&&n<=100){for(int i=2;i<=2000;i++)//从第二步开始算{s=s*0.98;sum+=s;if(sum>=n){cout<<i<<endl;break;}}}}

数学方法

 #include<iostream>#include<cmath>using namespace std;int main(){double n;cin>>n;double a=2.0;double sum=2.0;if(n<=2){cout<<"1"<<endl;}else if(n>2&&n<=100){int x=ceil(log(1-1.0*(n*(1-0.98))/a)/log(0.98));//计算xfor(int i=2;i<=x;i++){a=a*0.98;sum+=a;if(sum>=n){cout<<i<<endl;break;}}}}

P1420 最长连号

题目描述

输入长度为 nn 的一个正整数序列，要求输出序列中最长连号的长度。

连号指在序列中，从小到大的连续自然数。

 #include<iostream>#include<cmath>using namespace std;int main(){int n;cin>>n;int a[n]={0};cin>>a[0];int f=a[0];int count=0;int b=0;for(int i=1;i<n;i++){cin>>a[i];//判断是否连号if(f==a[i]-1){count++;}else//否，次数置零{count=0;}//比较连号长度if(count>=b){b=count;}	f=a[i];//重置f}b++;//count++表示第一个数后面连号的次数，最后要加上第一个数cout<<b<<endl;//输出}

P1089 [NOIP 2004 提高组] 津津的储蓄计划

题目描述

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300300 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 20%20% 还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 100100 元或恰好 100100 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如 1111月初津津手中还有 8383 元，妈妈给了津津 300300 元。津津预计1111月的花销是 180180 元，那么她就会在妈妈那里存 200200 元，自己留下 183183 元。到了 1111 月月末，津津手中会剩下 33 元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据 20042004 年 11 月到 1212 月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到 20042004 年年末，妈妈将津津平常存的钱加上 20%20% 还给津津之后，津津手中会有多少钱。

代码

 #include<iostream>using namespace std;int main(){int a[12]={0};for(int i=0;i<12;i++){cin>>a[i];}int b=0;int sum=0;bool flag =true;for(int i=0;i<12;i++){int c=3;//整百数量for(int j=1;j<=3;j++)//计算当月剩整百的数量及这个月总钱{if(sum<a[i]){sum+=100;c--;}else{break;}}sum=sum-a[i];//当月月余if(sum<0)//判断是否有月余{cout<<'-'<<i+1<<endl;flag=false;break;}else{b+=c;//整百数累加}}if(flag)//输出总钱{cout<<b*120+sum<<endl;}return 0;}

小总结