神奇数

import java.util.*;
	public class Main {
	    public static void main(String[] args) {
	        Scanner in = new Scanner(System.in);
	        int begin = in.nextInt();
	        int end = in.nextInt();
	        if(end < 10) {
                in.close();
                System.out.println("count= " + 0);
	            return;
	        }
	        int count = 0;
	        for(int m=begin; m<=end; m++) {
	            int num = m;
	            boolean isMagic = false;
	            ArrayList<Integer> a = new ArrayList<>();
	            while(num != 0) {
	                a.add(num % 10);
	                num /= 10;
	            }
	            for(int i=0; i<a.size(); i++) {
	                if(a.get(i) == 0) {
	                    continue;
	                }
	                for(int j=0; j<a.size(); j++) {
	                    if(i == j) {
	                        continue;
	                    }
	                    int tmp = a.get(i) * 10 + a.get(j);
	                    if(isPrime(tmp)) {
	                        isMagic = true;
	                        break;
	                    }
	                }
	                if(isMagic) {
	                    count ++;
	                    break;
	                }
	            }
	        }
	        System.out.println(count);
            in.close();
	    }
	    public static boolean isPrime(int n) {
	        int i = 2;
	        while(i<n && (n%i != 0)) {
	            i++;
	        }
	        return i == n;
	    }
	}

function countNum(a, b) {
   var num = [];
   for(var i = a+1; i < b; i++) {
     i.toString().split('').map((v, j) => {
       i.toString().split('').map((val, o) => {
         if (j!==o) {
           var k = v + val, t=0;
           for(var w = 1; w <= k; w++) {
             if (k%w === 0) {
               t++;
             }
           }
           if (t === 2 && k >10) {
             num.push(i);
           }
         }
       })
     })
   }
   return num.filter((x, i, s) => x && s.indexOf(x) === i).length;
 }
代码一直过不了，我也不知道为什么

思路

枚举这个区间内的所有整数x，然后将x转成字符串做全排列，取2个字符组合得到整数y，如果y是质数，它就是神奇数，计数器++。

因为是全排列，所以不论整数有多少位，只要取前两个数字就能保证取到所有情况，使用stoi函数，顺便处理了前导0的情况。

代码

#include <bits/stdc++.h>
using namespace std;

bool is(int x)
{
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return false;
    return true;
}

bool check(string& s)
{
    do
    {
        string t;
        t.push_back(s[0]);
        t.push_back(s[1]);
        if (is(stoi(t)) && stoi(t) >= 11) return true;
    } while (next_permutation(s.begin(), s.end()));
    return false;
}

int main()
{
    int a, b;
    cin >> a >> b;
    int res = 0;
    for (int i = a; i <= b; i++)
    {
        string s = to_string(i);
        sort(s.begin(), s.end());
        if (check(s)) res++;
    }
    cout << res << endl;
    return 0;
}

• 时间复杂度：。是范围内整数的个数。

反思：考试时这道题没有通过，主要有两个原因。

1. 使用next_permutation()函数之前要对字符串做排序，确保从最小的排列开始，从而生成所有可能的排列组合。否则会漏掉一些情况，这是我之前不知道的。
2. stoi(t) >= 11保证了组合数t的2位数都不是0，这样才符合题意。

这道题处理的质数范围是2位数的，所以可以将2位数的质数放在表中，这样就可以直接查表判断质数了。另外判断素数的函数首先要判断x<2的情况，这道题因为x一定是2位数的，所以就没有写。

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
bool isPrime(int n)
{
    if(n<11)
        return false;
    for(int i=2; i<=sqrt(n); i++)
        if(n%i==0)
            return false;
    return true;
}
bool isMagic(int n)
{
    if(n<11)
        return false;
    vector<int> v;
    while(n)
    {
        v.push_back(n%10);
        n/=10;
    }
    for(int i=0; i<v.size()-1; i++)
        for(int j=i+1; j<v.size(); j++)
            if(isPrime(v[i]*10+v[j])||isPrime(v[j]*10+v[i]))
                return true;
    return false;
}
int main()
{
    int a,b;
    cin>>a>>b;
    int sum=0;
    for(int i=a; i<=b; i++)
        if(isMagic(i))
            sum++;
    cout<<sum<<endl;
    return 0;
}

def text():
    li = list(map(int,input().split()))
    j = 1
    zhi = [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91,97]
    b = {}
    for z in range(int(li[0]),int(li[-1])+1):
        new_li = list(str(z))
        a = []
        for i in range(len(new_li)):
            for l in range(j,len(new_li)):
                if i == l:
                    continue
                a.append(new_li[i]+new_li[l])
                j = 0
        for i in set(a):
            if int(i) in zhi:
                b[z] = 1
    print(len(b))
text()

while(line=readline()){
    var lines = line.split(" ");
    var a = parseInt(lines[0]);
    var b = parseInt(lines[1]);
     
    print(qujian(a,b));
}
function qujian(a,b){
    var count =0;
    for(var i=a;i<=b;i++){
        if(level(i)){
            ++count
        }
    }
    return count
}
function level(n){
    var strN = n.toString()
    var len = strN.length
    if(len==1){
        return false
    }
    for(var i=0;i<len;i++){
        for(var j=0;j<len;j++){
            if(j==i){
                continue
            }
            if(strN[i] ==0){
                continue
            }
            var newStr=strN[i]+strN[j]
            var numStr= parseInt(newStr)
            if(checkNum(numStr)){
                return true
            }
            else{
                continue
            }
                 
        }
    }
    return false
}
function checkNum(n){
    for(var i=2;i<=Math.sqrt(n);i++){
        if(n%i==0){
            return false
        }
    }
    return true
}

#include<iostream>
#include<math.h>
#include <sstream>
#include <cstring>

bool IS_Prime(const int num)
{
    //1 is not prime
    if(num == 1) return false;
    
    int i = 2;
    while( i * i <= num)
    {
        if(num % i == 0)
            return false;
        i += 1;
    }
    return  true;
}

bool GetNum_OF_Prime(unsigned int num,unsigned int * numb,int size)
{
    memset(numb,0,size * sizeof(unsigned int));
   
    unsigned int N;
    for (N = 0; num; N++)
    {
        numb[N] = num % 10;
        num /= 10;
    }
    
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j)continue;
            if (numb[i] != 0 && IS_Prime(numb[i] * 10 + numb[j]))
                return true;
        }
    }
    return false;
}

int main(int argc, const char * argv[])
{
    unsigned int a, b;
    while(std::cin >> a >> b)
    {
        std::stringstream ss;
        ss << b;
        int max_num_len = ss.str().length(); //get the max num length for the arr  lenght
        unsigned int * arr = new unsigned int [max_num_len];
        
        unsigned int prime_count = 0;
        for (unsigned int i = a; i <= b; i++)
        {
            if (GetNum_OF_Prime(i,arr,max_num_len))
                prime_count++;
        }
        delete [] arr;
        std::cout << prime_count << std::endl;
    }

    return 0;
}

import java.util.Scanner;

/*
 * 想不到更好的办法只能暴力求解了,遍历[a,b]中每个数，然后任取两位判断组成的二位数是否是质数
 * */
public class ShenQi {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            int count = 0;
            for (int i = a; i <= b; i++) {
//                通过字符转换
                String tmp = i + "";
                boolean flag = false;
//                任意取两位
                for (int j = 0; j < tmp.length() - 1; j++) {
                    for (int k = j + 1; k < tmp.length(); k++) {
                        int first = (tmp.charAt(j) - '0') * 10 + tmp.charAt(k) - '0';
//                        必须构成二位数
                        if (first > 10 && isPrime(first)) {
                            count++;
                            flag = true;
                        } else {
                            int second = (tmp.charAt(k) - '0') * 10 + tmp.charAt(j) - '0';
                            if (second > 10 && isPrime(second)) {
                                count++;
                                flag = true;
                            }
                        }
//                        符合条件直接跳出
                        if (flag) {
                            break;
                        }
                    }
                    if (flag) {
                        break;
                    }
                }
            }
            System.out.println(count);
        }
    }

    private static boolean isPrime(int n) {
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

pyhon3 ，强烈推荐itertools.combinations import itertools
a, b = map(int, input().split())
# 生成所有的两位质数
zs = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
# 求得满足条件的神奇数
num = 0
for i in range(a, b + 1):  # i=15
    tt = list(str(i))
    for item in itertools.combinations(tt, 2):
        tep = [int("".join(item)), int("".join(item[::-1]))]
        for j in tep:
            if j in zs and j >= 10:
                num+=1
                break
        else:
            continue
        break
print(num)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        List<Integer> primeList=new ArrayList<Integer>();
        for(int i=11;i<100;i++)
        {
            boolean isPrime=true;
            for(int j=2;j<=Math.sqrt(i);j++)
            {
                if(i%j==0)
                {
                    isPrime=false;
                    break;
                }
            }
            if(isPrime)
            {
                primeList.add(i);
            }
        }

        Scanner scanner=new Scanner(System.in);
        int start=scanner.nextInt();
        int end=scanner.nextInt();
        int count=0;
        loop1: for(int num=start;num<=end;num++)
        {
            String numStr=String.valueOf(num);
            for(int primeNum:primeList)
            {
                String primeStr=String.valueOf(primeNum);
                if(isComContain(primeStr, numStr))//这个数包含质数的每一位
                {
                    count++;//这个数是神奇数
                    continue loop1;
                }
            }
        }
        System.out.println(count);
    }

    /**
     * 判断parent是否包含child中的每一个字符。注意：“132”不包含“11”
     * @param child
     * @param parent
     * @return
     */
    public static boolean isComContain(String child,String parent)
    {
        for(int i=0;i<child.length();i++)
        {
            String childTmp=child.substring(i,i+1);
            if(!parent.contains(childTmp))
            {
                return false;
            }
            parent=parent.replaceFirst(childTmp, "");
        }

        return true;
    }
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

static int length = 0;
int arr[4] = {2, 3, 5, 7};

bool isPrime(int n) {
    if (n < 10) {
        return false;
    }
    for (int i = 0; i < 4; i++) {
        if (n % arr[i] == 0) {
            return false;
        }
    }
    return true;
}

int checkBit(int n) {
    int i = 0;
    while (n != 0) {
        n /= 10;
        i++;
    }
    return i;
}

//合并字符数组中相同的字符，并同时去掉‘0’
char* combSameCh(char* ch, int len) {
    int i = 0;
    while (i < len - 1) {
        if (ch[i] == ch[i + 1] && ch[i] != '1') {
            for (int j = i; j < len - 1; j++) {
                ch[j] = ch[j + 1];
            }
            len--;
        }
        i++;
    }
    i = 0;
    while (i < len) {
        if (ch[i] == '0') {
            for (int j = i; j < len - 1; j++) {
                ch[j] = ch[j + 1];
            }
            len--;
        }
        i++;
    }
    length = len;
    return ch;
}

int main(int argc, const char * argv[]) {
    int a, b, result = 0;
    cin >> a >> b;
    for (int i = a; i <= b ; i++) {
        char numCh[10];
        sprintf(numCh, "%d", i);
        sort(numCh, numCh + checkBit(i));
        char *temp = combSameCh(numCh, checkBit(i));
        strcpy(numCh, temp);    //很无奈，直接给temp会报错。char[]赋给char*没问题，反之就报错。
        bool isMagic = false;
        for (int j = 0; j < length - 1; j++) {
            for (int k = j + 1; k < length; k++) {
                int num1 = (int)(numCh[j] - '0');
                int num2 = (int)(numCh[k] - '0');
                int cond1 = num1 * 10 + num2;
                int cond2 = num2 * 10 + num1;
                if (isPrime(cond1) || isPrime(cond2)) {
                    result++;
                    isMagic = true;
                    break;
                }
            }
            if (isMagic) {
                break;
            }
        }
    }
    cout << result;
    return 0;
}