C++——素数（质数）专题训练2

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
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 
2.密码质数：passprime 
【题目描述】 
因为素数没有1以外的因数，而且素数排列也完全没有规律，因此常被用来做为生成密码的基础。牛博士想从5000以内的素数表中选取若干个素数用来生成密码。你是牛博士的助手，主动提出要帮牛博士找来些素数。
 
【输入】 
输入文件有多行，第一行为数值N，表示需要N个素数，N<=1000。
 
接下来的N行，每行一个数i，代表素数表中的第i个数，素数表的第一个数是2
 
【输出】 
有N行数据，每行一个数为按要求找到的素数。
 
【样例输入】 
3
1
5
3
 
【样例输出】 
2
11
5
 
#include
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 
3.重排质数 sortprime 
【题目描述】 
牛博士上次的实验失败了，经过仔细的分析和研究，发现原来只在N个实验数据中找出素数是不够的，还要对这些素数进行排序，并标出该素数在原来N个数据中的位置。
 
【输入】 
输入文件有多行，第一行为数值N，N<=1000
 
接下来的N行，每行一个实验数据，每个数据<=10000
 
【输出】 
有多行数据，按字典序输出实验数据中的素数，以及该素数在原数据中的位置。
 
每行有两个数用空格隔开，第一个数是找到的素数，第二个数是该素数在原数据中的位置.
 
【样例输入】 
5
1
11
5
6
7
 
【样例输出】 
5 3
7 5
11 2
 
#include
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;jb[j])
			{
			  swap(b[i],b[j]);swap(c[i],c[j]);//从小到大排序 
			} 
		}
	}
	for(int i=1;i<=s;i++)
	{
        cout< 
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
using namespace std;
int main()
{
	int n,head=1,tail=1,x;//head和tail分别表示特殊质数的范围(头和尾) 
	bool p;
	cin>>n;
	for(int i=1;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5650480.html