得物笔试得物笔试题 0906

笔试时间：2025年9月6日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

小明最近刚刚学习完素数的概念，老师出了一个课后练习。问题是：如果将一个n (n ≥ 2)位的素数拆分成两部分，其中高m位是一个素数，低(n - m)位也是一个素数，那么这个素数称为可拆分素数。

例如：113是一个素数，它可以拆成两部分：

高两位11是一个素数
低一位3也是一个素数因此113是一个可拆分素数。

现在输入两个正整数M和N (M < N)，请编写一个程序计算M到N之间有多少个可拆分素数（包含M和N）。

输入描述

输入两个正整数M和N，其中10 ≤ M < N ≤ 10^6，数字间空格隔开。

输出描述

输出M和N之间可拆分素数的个数（包含M和N）。

样例输入

10 100

样例输出

4

参考题解

解题思路：

使用埃拉托斯特尼筛法预处理所有小于等于10^6的素数

对每个素数，将其转换为字符串，枚举所有可能的拆分点

判断拆分后的高位和低位是否都是素数

统计满足条件的可拆分素数个数

C++：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

const int MAX = 1000000;
bool isPrime[MAX + 1];

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

bool isSplittablePrime(int num) {
    string str = to_string(num);
    int len = str.length();
    for (int i = 1; i < len; i++) {
        int high = stoi(str.substr(0, i));
        int low = stoi(str.substr(i));
        if (isPrime[high] && isPrime[low]) {
            return true;
        }
    }
    return false;
}

int main() {
    sieve();
    int M, N;
    cin >> M >> N;
    int count = 0;
    for (int num = M; num <= N; num++) {
        if (isPrime[num] && isSplittablePrime(num)) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Java：

import java.util.*;

public class Main {
    static final int MAX = 1000000;
    static boolean[] isPrime = new boolean[MAX + 1];
    
    static void sieve() {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= MAX; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= MAX; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
    
    static boolean isSplittablePrime(int num) {
        String str = Integer.toString(num);
        int len = str.length();
        for (int i = 1; i < len; i++) {
            int high = Integer.parseInt(str.substring(0, i));
            int low = Integer.parseInt(str.substring(i));
            if (isPrime[high] && isPrime[low]) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sieve();
        int M = sc.nextInt();
        int N = sc.nextInt();
        int count = 0;
        for (int num = M; num <= N; num++) {
            if (isPrime[num] && isSplittablePrime(num)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Python：

MAX = 1000000
isPrime = [True] * (MAX + 1)

def sieve():
    isPrime[0] = isPrime[1] = False
    i = 2
    while i * i <= MAX:
        if isPrime[i]:
            j = i * i
            while j <= MAX:
                isPrime[j] = False
                j += i
        i += 1

def is_splittable_prime(num):
    s = str(num)
    length = len(s)
    for i in range(1, length):
        high = int(s[:i])
        low = int(s[i:])
        if isPrime[high] and isPrime[low]:
            return True
    return False

sieve()
M, N = map(int, input().split())
count = 0
for num in range(M, N + 1):
    if isPrime[num] and is_splittable_prime(num):
        count += 1
print(count)