蓝桥杯准备 【入门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为true
int 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));//计算x
for(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;
}