给出一个区间[a, b],计算区间内“神奇数”的个数。
神奇数的定义:存在不同位置的两个数位,组成一个两位数(且不含前导0),且这个两位数为质数。
比如:153,可以使用数字3和数字1组成13,13是质数,满足神奇数。同样153可以找到31和53也为质数,只要找到一个质数即满足神奇数。
输入为两个整数a和b,代表[a, b]区间 (1 ≤ a ≤ b ≤ 10000)。
输出为一个整数,表示区间内满足条件的整数个数
11 20
6
#include<iostream> #include <math.h> #include <vector> using namespace std; bool isPrime(int num){ for(int i=2;i<=sqrt(num);i++){ if(num%i==0) return false; } return true; } int main(){ int a,b; while(cin>>a>>b){ if(b<10){ cout<<0<<endl; return 0; } int count=0; for(int i=a;i<=b;i++){ vector<int> arr; int temp=i; while(temp){ arr.push_back(temp%10); temp/=10; } int flag=0; for(int j=0;j<arr.size();j++){ for(int k=0;k<arr.size();k++){ if(k==j) continue; int prime=arr[j]*10+arr[k]; if(prime<10) continue; if(isPrime(prime)){ flag=1; break; } } if(flag) break; } if(flag) count++; } cout<<count<<endl; } return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ List<Integer>list = 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) list.add(i); } Scanner scanner = new Scanner(System.in); int a = scanner.nextInt(); int b = scanner.nextInt(); int cnt = 0; for(int i=a;i<=b;i++){ String s = String.valueOf(i); for(Integer e: list){ String s1 = String.valueOf(e/10); String s2 = String.valueOf(e%10); if(!s1.equals(s2)){ if(s.indexOf(s1)!=-1&&s.indexOf(s2)!=-1){ cnt++; break; } }else{ int index = s.indexOf(s1); if(index!=-1&&s.indexOf(s2, index+1)!=-1){ cnt++; break; } } } } System.out.println(cnt); } }
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; } }
}return flag?1:0;
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; } 代码一直过不了,我也不知道为什么
#include <bits/stdc++.h> using namespace std; bool is_prime[100]; bool check(int x) { string s = to_string(x); for(int i = 0; i < s.size(); i++) { for(int j = 0; j < s.size(); j++) { if(s[i] == '0' || i == j) continue; int num = 10*(s[i] - '0') + (s[j] - '0'); if(is_prime[num]) return true; } } return false; } int main() { is_prime[11] = is_prime[13] = is_prime[17] = is_prime[19] = is_prime[23] = is_prime[29] = is_prime[31] = is_prime[37] = is_prime[41] = is_prime[43] = is_prime[47] = is_prime[53] = is_prime[59] = is_prime[61] = is_prime[67] = is_prime[73] = is_prime[79] = is_prime[83] = is_prime[89] = is_prime[91] = is_prime[97] = true; int a, b; cin >> a >> b; int ans = 0; for(int x = a; x <= b; x++) { if(x < 10) continue; ans += check(x); } cout << ans << endl; return 0; }
#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;
}
#include<iostream> #include<vector> using namespace std; int main(int argc, char * agrv[]) { int s; cin >> s; int e; cin >> e; char bitmap[13] = { 0 }; bitmap[0] = 1 << 7 & 1 << 6; for (int i = 2; i < 100; i++) { if (!(bitmap[i / 8] & (1 << (7 - i % 8)))) { for (int q = i + i; q < 100; q += i) { bitmap[q / 8] |= (1 << (7 - q % 8)); } } } int count = 0; for (int i = s; i <= e; i++) { vector<int> digit; int j = i; while (j > 0) { digit.push_back(j % 10); j /= 10; } bool magic = false; for (auto q = 0; q < digit.size(); q++) { for (auto p = 0; p < digit.size(); p++) { if (p != q && digit[q] !=0) { int tar = digit[q] * 10 + digit[p]; if (!(bitmap[tar / 8] & (1 << (7 - tar % 8)))) { magic = true; count++; break; } } } if (magic) break; } } cout << count << endl; return 0; }利用bitmap最大限度压缩内存
import java.util.*; public class Main{ private static boolean getPrime(int num){ boolean flag=true; for(int i=2;i<num;i++){ if(num%i==0){ flag=false; return false; } } return flag; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int num1=sc.nextInt(); int num2=sc.nextInt(); int count=0; if(num2<10){ System.out.println(0); sc.close(); } for(int j=num1;j<=num2;j++){ ArrayList <Integer> list=new ArrayList<Integer>(); boolean res=false; int num=j; while(num!=0){ list.add(num%10); num=num/10; } for(int k=0;k<list.size();k++){ if(list.get(k)==0){ continue; //表示0不能作为前置,其次0不能作为个位(偶数); } for(int l=0;l<list.size();l++){ if(l==k){ continue; //表示取得相同位置元素,则继续下次循环; } if(list.get(l)==0){ continue; } int tmp=list.get(k)*10+list.get(l); if(getPrime(tmp)){ res=true; break; //跳出循环体进行判断; } } if(res){ count++; break; //跳出外层循环; } } } System.out.println(count); } sc.close(); } }