腾讯2017招聘第三题

素数对

题目描述

给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）

输入描述:

输入包括一个整数n,(3 ≤ n < 1000)

输出描述:

输出对数

解法分析

step 1: 将所有范围内的素数存入表中(时间复杂度$O(n^2)$, 空间复杂度$O(n)$).
step 2: 从2开始遍历到n / 2, 找到数对的总数.

这是我的解法,不保证最优.腾讯的四个题表面上看都不难,应该都可以撸出来才对啊.我还要再仔细看一下才行.还要准备做好面试的准备.

代码

#include <iostream>
using namespace std;
int find_prime(int *a, int length, int n);
bool binary_find(const int *a, int length, int from, int to, int target);
int main() {
    int a[1000];
    int n;
    cin >> n;
    int mid = n / 2;
    int count = find_prime(a, 1000, n);
    int num_couple = 0;
    for(int i = 2; i <= mid; i++)
    {
        if(binary_find(a, 1000, 0, count - 1, i)
           && binary_find(a, 1000, 0, count - 1, n - i))
            num_couple += 1;
    }
    cout << num_couple;
    return 0;
}

int find_prime(int *a, int length, int n)
{
    int count = 0;
    bool flag = true;
    for(int i = 2; i < n; i ++)
    {
        for(int j = 2; j < i; j++)
        {
            if(i % j == 0)
            {
                flag = false;
                break;
            }
        }
        if(flag)
            a[count++] = i;
        flag = true;
    }
    return count;
}
bool binary_find(const int* a, int length, int from, int to, int target)
{
    while(from <= to)
    {
        int mid = (from + to) / 2;
        if(a[mid] > target)
            to = mid - 1;
        else if(a[mid] < target)
            from = mid + 1;
        else
            return true;
    }
    return false;
}