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;
}