C++——素数（质数）专题训练
作者有话说：本篇共8道题，从易到难的顺序，都是较为常见的题目类型，后续还会补充有关素数（质数）的有关练习题。
1.素数个数
【题目描述】
“六一”儿童节到了，五年级2班的朱老师组织了数素数游戏，游戏规则是这样的：张老师任意给出一个正整数M，参加游戏者说出1至M之间（包括1和M）素数的个数，谁最先说出正确的答案将会得到一个奖品。现在请你编写一个程序对给出的M，输出正确的答案。
【输入】
输入只有一个正整数M（M为小于30000的正整数）
【输出】
输出只有一个数，就是1到M之间的素数的个数。
【样例输入】
20
【样例输出】
8
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,s=0;bool p;
cin>>m;
for(int i=2;i<=m;i++)//1不是质数
{
p=true;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
p=false;break;//不是质数 跳出循环
}
}
if(p==true) s++;
}
cout<<s;
return 0;
}2.素数的和
【题目描述】
如果一个整数只能被1和它本身整除，这样的数就叫素数。编程输入n和m（n、m在2和200之间，且n<m），求n,m之间所有素数的和。
【输入格式】
n m
【输出格式】
s(n~m之间所有素数的和)
【样例输入】
2 10
【样例输出】
17
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,s=0;bool p;
cin>>n>>m;
for(int i=n;i<=m;i++)
{
p=true;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
p=false;break;//不是质数 跳出循环
}
}
if(p==true&&i!=1) s=s+i;//1不是质数
}
cout<<s;
return 0;
}3.个位数为1的素数
【题目描述】
输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。
【输入】
一行，输入n。
【输出】
输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开)，如果没有则输出-1。
【样例输入】
70
【样例输出】
11 31 41 61
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;bool p,w=false;
cin>>n;
for(int i=2;i<n;i++)//注意：根据题目要求不包括1和这个整数
{
p=true;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
p=false;break;//不是质数 跳出循环
}
}
if(p==true&&i%10==1)
{
cout<<i<<" ";
w=true;//说明有满足题目要求的素数
}
}
if(w==false) cout<<-1;
return 0;
}4.求第n小的质数
【题目描述】
输入一个正整数n，求第n小的质数。
【输入】
一个不超过10000的正整数n。
【输出】
第n小的质数。
【样例输入】
10
【样例输出】
29
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,i=1,s=0;bool p;
cin>>n;
while(n)
{
p=true;i++;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
p=false;break;
}
}
if(p==true)
{
s++;
if(s==n)
{
cout<<i;break;//找到第n小的质数 跳出循环
}
}
}
return 0;
}5.回文素数
【题目描述】
如果一个数从左边读和从右边读都是同一个数, 就称为回文数，既是素数又是回文数的数，称为回文素数。找出某个范围内的回文素数。
【输入】
整数m和n，2=<m<n<=106。
【输出】
m~n范围内的所有回文素数，从小大到排列，每行10个数。
【样例输入】
5 500
【样例输出】
5 7 11 101 131 151 181 191 313 353
373 383
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,n,x,xin,s=0;bool p;
cin>>m>>n;
for(int i=m;i<=n;i++)
{
p=true;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
p=false;break;
}
}
if(p==true)//先判断满足素数条件，接着判断是否是回文数
{
x=i;xin=0;
while(x!=0)
{
xin=xin*10+x%10;//逆序数
x/=10;//去掉个位数
}
if(xin==i)//既是素数又是回文数
{
s++;//计数
if(s%10==0) cout<<i<<endl;//输出并换行
else cout<<i<<" ";//输出并空格
}
}
}
return 0;
}6.绝对素数
【题目描述】
绝对素数是指本身是素数，其逆序数也是素数的数。例如：10321与12301是绝对素数。编写一个程序，求出所有m~n（m≥11，n≤1000000）之间的绝对素数。
【输入】
两个整数m和n。
【输出】
m~n之间的绝对素数，每个数之间用空格隔开，每行输出10个
【样例输入】
11 300
【样例输出 】
11 13 17 31 37 71 73 79 97 101
107 113 131 149 151 157 167 179 181 191
199
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,n,x,xin,s=0;bool p,w;
cin>>m>>n;
for(int i=m;i<=n;i++)
{
x=i;xin=0;p=true;w=true;
while(x!=0)
{
xin=xin*10+x%10;
x/=10;
} //得出逆序数
for(int j=2;j<i;j++)
{
if(i%j==0)
{
p=false;break;//判断本身是否素数
}
}
for(int j=2;j<xin;j++)
{
if(xin%j==0)
{
w=false;break;//判断逆序数是否素数
}
}
if(p==true&&w==true)
{
s++;
if(s%10==0) cout<<i<<endl;
else cout<<i<<" ";
}
}
return 0;
}7.孪生素数
【题目描述】
在质数的大家庭中，大小之差不超过2的两个质数称它俩为一对孪生素数，如2和3、3和5、17和19等等。请你统计一下，在不大于自然数N的质数中，孪生素数的对数。
【输入】
只有一行，一个自然数N。(N<=100 0000)。
【输出】
只有一行，一个整数，表示N以内孪生素数的对数。
【样例输入】
20
【样例输出】
5
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,s=0;bool p,w;
cin>>n;
for(int i=2;i<n;i++)
{
p=true;
for(int j=2;j<i;j++)
{
if(i%j==0)
{
p=false;break;
}
}
for(int z=i+1;z<=i+2;z++)//判断的范围不超过 2
{
w=true;
for(int j=2;j<z;j++)
{
if(z%j==0)
{
w=false;break;
}
}
if(p==true&&w==true)
s++;
}
}
cout<<s;
return 0;
}8.纯粹素数（不确定位数）
【题目描述】
纯粹素数是这样定义的：一个素数，去掉最高位，剩下的数仍为素数，再去掉剩下的数的最高位，余下的数还是素数。这样下去一直到最后剩下的个位数也还是素数。输入一个整数N，如果是纯粹素数输出yes，否则输出no。
【输入】
正整数N，N<=10^9。
【输出】
yes或者no，yes表示N是纯粹素数，no表示N不是纯粹素数。
【样例输入】
1013
【样例输出 】
yes
解析：举例N为2131，按照1、31、131、2131的顺序依次判断是否为素数。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x,s=0,mod=1;bool p=true;
cin>>n;
x=n;
while(x!=0)
{
s++;
x/=10;
}//先判断 n 为几位数
for(int i=1;i<=s;i++)
{
mod*=10;
x=n%(mod);//从低位到高位依次判断
for(int j=2;j<x;j++)
{
if(x%j==0)
{
p=false;break;
}
}
}
if(p==true&&n!=1) cout<<"yes";
else cout<<"no";
return 0;
}