神奇数--全国模拟（三）

[编程题] 神奇数

时间限制：1秒

空间限制：32768K

给出一个区间[a, b]，计算区间内“神奇数”的个数。

神奇数的定义：存在不同位置的两个数位，组成一个两位数（且不含前导0），且这个两位数为质数。

比如：153，可以使用数字3和数字1组成13，13是质数，满足神奇数。同样153可以找到31和53也为质数，只要找到一个质数即满足神奇数。 

输入描述:

输入为两个整数a和b，代表[a, b]区间 (1 ≤ a ≤ b ≤ 10000)。

 

 

输出描述:

输出为一个整数，表示区间内满足条件的整数个数

 

输入例子:

11 20

 

输出例子:

6

 

解题思路：

1）遍历a-b  特殊情况判断如果b<=10  输出0，如果a<=10 a=11

2）将数按位存在wei中，然后在wei中取两位组成result1和result2

3）判断result1和result2是否为质数

 

本题注意：题目中1 ≤ a ≤ b ≤ 10000实际测试时例子11 11111没有进行b的范围的判断，因此不需要管题目说明中b的最大范围

 

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int a;
    int b;
    vector<int> wei1;//倒序存储每一位
    vector<int> wei;//正序存储每一位
    int tmp;
    int result1 = 0;
    int result2 = 0;
    while(cin>>a>>b)
    {
        int count=0;
        int num = 0;
        if(b <= 10)
            cout<<count<<endl;
        else
        {
            if(a<=10)
                a = 11;
            for(int i=a;i<=b;i++)
            {
                num=0;
                tmp = i;
                while(tmp)
                {
                    wei1.push_back(tmp%10);
                    tmp = tmp/10;
                }
                for(int x=wei1.size()-1;x>=0;x--)
                {
                    wei.push_back(wei1[x]);
                }
                
 
                for(int k=0;k<wei.size();k++)
                {
                    for(int z=k+1;z<wei.size();z++)
                    {
                        num = 0;//此处别忘了num置0
                        result1 = wei[k]*10+wei[z];
                        result2 = wei[z]*10+wei[k];
                        //判断result是否为质数
                        if(result1/10 == 0)
                        {
                            result1 = 0;
                            num++;
                        }
 
                        for(int j=2;j<result1;j++)
                        {
                            if(result1%j==0)
                            {
                                num++;
                            }
                        }
                        if(num == 0)
                        {
                            break;
                        }
 
                        else
                        {
                            num = 0;
                            if(result2/10 == 0)
                            {
                                result2 = 0;
                                num++;
                            }
 
                            for(int j=2;j<result2;j++)
                            {
                                if(result2%j==0)
                                {
                                    num++;
                                    break;
                                }
                            }
                            if(num == 0)
                            {
                                break;
                            }
                        }
                    }
 
                    if(num == 0)
                    {
                        count++;
                        break;
                    }
                }
                wei.clear();
                wei1.clear();
            }
        }
        cout<<count<<endl;
    }
}

 更好的方法：

#include <bits/stdc++.h>
 
using namespace std;
 
bool isprime(int x) {
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}
bool check(int x) {
    int cnt[10];
    memset(cnt, 0, sizeof(cnt));
    //此步骤相当于去重了数字，保证相同的数字存在相同位置
    while(x) {
        cnt[x % 10]++;
        x /= 10;
    }
    for(int i = 1; i < 10; i++) {
        for(int j = 1; j < 10; j++) {
            //取出两个不同的数
            if(i != j && cnt[i] && cnt[j]) {
                if(isprime(i * 10 + j)) return true;
            }
            //取出相同的数，且这个数字在原数中至少有两个
            else if(i == j && cnt[i] >= 2) {
                if(isprime(i * 10 + j)) return true;
            }
        }
    }
    return false;
}
int main() {
    int a, b, ans = 0;;
    cin >> a >> b;
    for(int i = a; i <= b; i++) {
        if(check(i)) ans++;
    }
    cout << ans << endl;
    return 0;
}