新华三软件开发工程师笔试 10-13

订阅专栏，方便查阅！！！

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

第一题

给定一个正整数n，求出小于等于n的所有素数，并输出它们。函数签名: public static ListfindPrimeNumbers(int n)

要求和提示: 素数(质数)是指只能被1和自身整除的正整数。1不是素数最小的素数是2。

可以使用暴力循环的方式判断每个数是否是素数，但效率较低。可以使用筛选法来提高效率。

可以使用数组或集合来存储素数。

注意边界条件和特殊情况的处理。

输入描述

n: 正整数，表示上限值

输出描述

返回一个List，包含小于等于n的所有素数。

示例1

输入

2

输出

2

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class Main3 {
public:
    static bool isPrime(int n) {
        if (n < 1) {
            return false;
        }
        if (n <= 3) {
            return true;
        }
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    static vector<int> getResult(int n) {
        vector<int> res;
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                res.push_back(i);
            }
        }
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> res = Main3::getResult(n);

    for (int prime : res) {
        cout << prime << " ";
    }
    cout << endl;

    return 0;
}

第二题

给定一个整数数组，编写一个程序来找到数组中两个数字之和等于目标值的下标。假设每个输入只有一个解，且不能重复使用相同的元素。

实现一个Solution类，其中包含一个方法twoSum，输入参数为一个整数数组nums和一个目标值target，返回两个数字之和等于目标值的下标。

输入描述

1, 2, 3;3 即表示输入 整数数组 nums=[1,2,3],目标值 target =3

输出

Indices: 0,1

#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

class Main1 {