2024年4月12日饿了么春招实习试题【第一题:质数和合数】-题目+题解+在线评测【模拟】

本文主要是介绍2024年4月12日饿了么春招实习试题【第一题:质数和合数】-题目+题解+在线评测【模拟】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

塔子哥有一个数组，她想知道这个数组不同的质数和不同的合数共有多少个。

合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数 (0除外) 整除的数。

输入描述

第一行入一个整数$1<=n<=2\times 10^5$表示数组长度。 第二行输入 n个整数表示数组$a_i(1<=a_i<=2\times 10^5)$

输出描述

输出一个整数。

样例

输入

3
20 2 4

输出

3

说明

不同的合数有20和4，质数有2，所以有3种。

OJ链接：
https://codefun2000.com/p/P1816

解题思路一：质数+合数＝除去1的所有正整数

除了1以外，一个大于0的整数要么是质数要么是合数，所以只需要计算集合的元素数量即可。如果数组包含1，则减去一个元素。

n = int(input())
nums = list(map(int, input().split()))
st = set(nums)
# if 1 in st:
#     print(len(st) - 1)
# else:
#     print(len(st))
print(len(st) - (1 if 1 in st else 0))

时间复杂度：O(n)
空间复杂度：O(n)

解题思路二：java

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class UniqueIntegers {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();Set<Integer> sett = new HashSet<>();for (int i = 0; i < n; i++) {int value = scanner.nextInt();sett.add(value);}int count = sett.size();if (sett.contains(1)) {count -= 1;}System.out.println(count);}
}

时间复杂度：O(n)
空间复杂度：O(1)

解题思路三：c++

#include <iostream>
#include <set>
using namespace std;
int main() {int n;cin >> n;set<int> sett;for (int i = 0; i < n; i++) {int value;cin >> value;sett.insert(value);}int count = sett.size();if (sett.find(1) != sett.end()) {count--;}cout << count << endl;return 0;
}

时间复杂度：O(n)
空间复杂度：O(1)

这篇关于2024年4月12日饿了么春招实习试题【第一题:质数和合数】-题目+题解+在线评测【模拟】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---