C++——素数（质数）专题训练2
作者有话说：万变不离其宗，本篇共4题，解题方法有很多种，主要考察学生阅读质数相关的应用题对其理解程度是否准确，后续更新新的专题。
1.线性筛素数
【题目描述】
如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。
【输入】
第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数。
接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。
【输出】
输出 q 行，每行一个正整数表示答案。
【样例输入】
100 5 1 2 3 4 5
【样例输出】
2 3 5 7 11
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,q,k,s;//n表示范围 q表示询问次数 k表示第k小
bool p;
cin>>n>>q;
for(int i=1;i<=q;i++)
{
cin>>k;s=0;
for(int j=2;j<=n;j++)
{
p=true;
for(int z=2;z<j;z++)
{
if(j%z==0)
{
p=false;break;
}
}
if(p==true)
{
s++;
if(k==s) cout<<j<<endl;
}
}
}
return 0;
}2.密码质数：passprime
【题目描述】
因为素数没有1以外的因数，而且素数排列也完全没有规律，因此常被用来做为生成密码的基础。牛博士想从5000以内的素数表中选取若干个素数用来生成密码。你是牛博士的助手，主动提出要帮牛博士找来些素数。
【输入】
输入文件有多行，第一行为数值N，表示需要N个素数，N<=1000。
接下来的N行，每行一个数i，代表素数表中的第i个数，素数表的第一个数是2
【输出】
有N行数据，每行一个数为按要求找到的素数。
【样例输入】
3 1 5 3
【样例输出】
2 11 5
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,s;
bool p;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>k;s=0;
for(int j=2;j<=5000;j++)
{
p=true;
for(int z=2;z<j;z++)
{
if(j%z==0)
{
p=false;break;
}
}
if(p==true)
{
s++;
if(k==s) cout<<j<<endl;
}
}
}
return 0;
}3.重排质数 sortprime
【题目描述】
牛博士上次的实验失败了，经过仔细的分析和研究，发现原来只在N个实验数据中找出素数是不够的，还要对这些素数进行排序，并标出该素数在原来N个数据中的位置。
【输入】
输入文件有多行，第一行为数值N，N<=1000
接下来的N行，每行一个实验数据，每个数据<=10000
【输出】
有多行数据，按字典序输出实验数据中的素数，以及该素数在原数据中的位置。
每行有两个数用空格隔开，第一个数是找到的素数，第二个数是该素数在原数据中的位置.
【样例输入】
5 1 11 5 6 7
【样例输出】
5 3 7 5 11 2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,s=0,a[10001],b[10001],c[1001];//a数组是输入的实验数据，b数组存质数，c数组存质数所在原数据中的位置
bool p;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];p=true;
for(int j=2;j<a[i];j++)
{
if(a[i]%j==0)
{
p=false;break;
}
}
if(p==true&&a[i]!=1)
{
s++;//是质数进行计数
b[s]=a[i];c[s]=i;//质数和所在位置分别存储到b数组和c数组
}
}
for(int i=1;i<=s;i++)
{
for(int j=i+1;j<=s;j++)
{
if(b[i]>b[j])
{
swap(b[i],b[j]);swap(c[i],c[j]);//从小到大排序
}
}
}
for(int i=1;i<=s;i++)
{
cout<<b[i]<<" "<<c[i]<<endl;
}
return 0;
}4.特殊的质数肋骨 Superprime Rib
【题目描述】
农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。
农民约翰确定他卖给买方的是真正的质数肋骨，是因为从右边开始切下肋骨，每次还剩下的肋骨上的数字都组成一个质数。
举例来说：7 3 3 1 全部肋骨上的数字 7331是质数；三根肋骨 733 是质数；二根肋骨 73 是质数；当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。
写一个程序对给定的肋骨的数目 n，求出所有的特殊质数。1 不是质数。
【输入】
一行一个正整数 n。
【输出】
按顺序输出长度为 n 的特殊质数,每行一个。
【样例输入】
4
【样例输出】
2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,head=1,tail=1,x;//head和tail分别表示特殊质数的范围(头和尾)
bool p;
cin>>n;
for(int i=1;i<n;i++)
{
head=head*10;
}
tail=head*10;
for(int i=head;i<tail;i++)
{
x=i;p=true;
while(x!=0)
{
for(int j=2;j<x;j++)
{
if(x%j==0)
{
p=false;break;
}
}
x=x/10;//从右开始切肋骨，依次判断是否为质数
}
if(p==true&&i/head!=1)//因为1不是质数 最高位为1的质数不能输出
cout<<i<<endl;
}
return 0;
}