B3939 [GESP样题 四级] 绝对素数 题解

一道经典的素数判断题。

1. 绝对素数定义:如果一个两位数是素数，把它的个位与十位交换，所得的数仍是素数，那么这个数就是绝对素数。

2. 关联题目: B2028,B3840。

3. 程序部分

• 素数判断:

  对于中间的for循环部分:

  其时间复杂度为 $O(\sqrt n)$

  详见:B3840题解 方法2

bool isPrime(int n){ //在bool类型中1为真，0为假。
    if(n<2) return 0; //也可改成if(n<=1) return 0;
    for(int i=2;i*i<=n;i++){ 
        if(n%i==0) return 0; //返回假 也可改为return false;
    }
    return 1; //返回真 也可改为return ture;
}

• 数字对换:

int n=i; 
int x=n/10%10; //个位
int y=n%10; //十位
n=y*10+x;

最后，附上完整代码:

#include <bits/stdc++.h> //万能头
using namespace std;
bool isPrime(int n){ //已经讲过的部分，不做解释
    if(n<2) return 0;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return 0;
    }
    return 1;
}
int main(){
	int a,b; //定义a,b
	cin>>a>>b; //输入a,b
    for(int i=a;i<=b;i++){ //从a循环到b
        if(isPrime(i)==1){ //如果i是素数
            int n=i; //使n=i
            int x=n/10%10;
            int y=n%10;
            n=y*10+x;
            //上3行已经讲过，不做解释
            if(isPrime(n)==1) cout<<i<<endl; //如果n也是素数，输出i
        }
    }
	return 0; //好习惯
}

第一次题解，写的不好的劳烦各位指出了。