思路
(暴力筛选)
从2到n-1依次循环判断该数是否为素数,若为素数,则将该素数转换为字符串(to_string方法), 判断字符串最后一个字符是否为‘1’即可。
C++ 代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
bool is_prime(int x) {
for(int i = 2; i <= x / i; i++) {
if(x % i == 0) return false;
}
return true;
}
int main() {
while(cin>>n) {
int cnt = 0;
for(int i = 2; i < n; i++) {
if(is_prime(i)) {
string s = to_string(i);
if(s[s.length() - 1] == '1') {
cnt++;
cout<<s<<" ";
}
}
}
if(cnt == 0) cout<<"-1"<<endl;
else cout<<endl;
}
return 0;
}
算法2
引入埃式筛改进
C++ 代码
#include<iostream>
using namespace std;
const int N = 10010;
bool st[N]; //false表示为素数
int prime[N];
int cnt;
void get_prime(int n) {
for(int i = 2; i < n; i++) {
if(!st[i]) {
string s = to_string(i);
if(s[s.length() - 1] == '1') prime[cnt++] = i;
}
for(int j = i + i; j <= n; j += i) st[j] = true;
}
}
int main() {
int n;
while(cin>>n) {
get_prime(n);
if(cnt != 0) {
for(int i = 0; i < cnt; i++)
cout<<prime[i]<<" ";
cout<<endl;
} else cout<<"-1"<<endl;
cnt = 0; //恢复现场
}
return 0;
}