[数据结构与算法]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;
}