递归形式的二分查找

题目

克里斯蒂安·哥德巴赫曾经猜想，每个奇合数可以写成一个素数和一个平方的两倍之和。

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

最终这个猜想被推翻了。

最小的不能写成一个素数和一个平方的两倍之和的奇合数是多少？

题目分析

涉及到的知识点

• 线性筛法找素数
• 二分查找（递归和非递归形式）

代码展示

关键逻辑见代码注释

#include<iostream>
using namespace std;
#define max_n 100000
int prime[max_n + 5] = {0};
int is_prime[max_n + 5] = {0};

void init() { // 线性筛
    for (int i = 2; i <= max_n; i++) {
        if (!is_prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0]; j++) {
            if (i * prime[j] > max_n) break;
            is_prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

int func(int n) { //分离被查找的函数，使代码变的模块化
    return 2 * n * n;
}

bool binary_search(int (*f)(int), int l , int r, int x) { // 函数作为参数的传递方式
    int mid = (l + r) / 2;
    if (l > r) return false;
    if (f(mid) == x) return true;
    if (f(mid) > x) r = mid - 1;
    else l = mid + 1;
    return binary_search(f, l, r, x); //递归形式的二分查找
}

int is_val(int x) {
    for (int i = 1; i <= prime[0] && prime[i] < x; i++) { // 判断条件放在循环内部，使代码更简洁
        int val = x - prime[i];
        if (binary_search(func, 1, val, val)) return true;
    }
    return false;
}

int main() {
    init();
    for (int i = 9; i <= max_n; i += 2) {
        if (!is_prime[i]) continue;
        if (is_val(i)) continue;
        cout << i << endl;
        break;
    }

    return 0;
}