首页 > 试题广场 >

神奇数

[编程题]神奇数

热度指数：3662 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个区间[a, b]，计算区间内“神奇数”的个数。
神奇数的定义：存在不同位置的两个数位，组成一个两位数（且不含前导0），且这个两位数为质数。
比如：153，可以使用数字3和数字1组成13，13是质数，满足神奇数。同样153可以找到31和53也为质数，只要找到一个质数即满足神奇数。

输入描述:

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

输出描述:

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

示例1

输入

11 20

输出

算法知识视频讲解

Java

jacksonary

package com.java24hours.mianshibaodian;

import java.util.Scanner;

/**

是我**，想太多，还给他添加了重复的验证，多此一举，还有搞不懂不是说了范围是1到10000,为什么测试的时候能达到8万多，算了，数组搞大一点就是了，代码如下：

* 判断给定范围内的神奇数的个数

* @author Weiguo Liu

public class shenqishu {

public static void main(String[] args) {

int count = 0;

int[] arr = new int[100000];

Scanner input = new Scanner(System.in);

String aa = input.next();

String bb = input.next();

int a = Integer.parseInt(aa);

int b = Integer.parseInt(bb);

for(int i=a;i<b+1;i++) {

count = isShenqi(i, count, arr);

}

System.out.println(count);

}

public static int isShenqi(int i, int count, int[] arr) {

String ii = String.valueOf(i);

int j,k;

for(j=0;j<ii.length();j++) {

//ii.charAt(j) + ""这里的意思是将char型转成String型

if(Integer.parseInt(ii.charAt(j) + "")!=0){

for(k=0;k<ii.length();k++){

if(k==j){

continue;

}else{

int m = Integer.parseInt(ii.charAt(j) + "") * 10;

m = m + Integer.parseInt(ii.charAt(k)+"");

if(isZhishu(m)) {

arr[count++] = m;

return count;

}

return count;

}

public static boolean isZhishu(int i) {

int k;

for(k=2;k<i/2+1;k++) {

if(i%k==0) {

break;

}

if(k < i/2+1){

return false;

}else {

return true;

}

//public static boolean notRe(int i, int[] arr) {

//int k;

//for(k=0;k<arr.length;k++) {

//if(arr[k]==i) {

//break;

//}

//if(k<arr.length) {

//return false;

//}else{

//return true;

//}

}

发表于 2017-06-11 14:40:34 回复(0)

Java

被遗忘的左手

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;
	    }
	}

编辑于 2017-06-06 23:26:22 回复(5)