给定n（n≤100）个正整数，所有正整数均≤100,000；求其中最大的那个素数。题目保证至少有一个素数。 例如给定序列： 4 5 6 2 3，最大素数为：5 给定序列： 6 7 3 4 5 ， 最大素数为：7 给定序列： 68 71 99 12 19 23 35 ， 最大素数为： 71 给定序列：14 5 69 51 89 31， 最大素数为：89。用python实现

可以使用以下代码实现：

import math

def is_prime(num):
if num == 2:
return True
if num < 2 or num % 2 == 0:
return False
for i in range(3, int(math.sqrt(num))+1, 2):
if num % i == 0:
return False
return True

n = int(input())
nums = list(map(int, input().split()))

max_prime = 0
for num in nums:
if is_prime(num) and num > max_prime:
max_prime = num

print(max_prime)

相关问题

给定n（n≤100）个正整数，所有正整数均≤100,000；求其中最大的那个素数。题目保证至少有一个素数。用python实现

以下是用 Python 实现的代码，它利用 Sieve of Eratosthenes 算法来找到最大的素数：

def maximum_prime(n, lst):
    sieve = [True] * (max(lst) + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(max(lst) ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * i, max(lst) + 1, i):
                sieve[j] = False
    for i in range(n-1, -1, -1):
        if sieve[lst[i]]:
            return lst[i]

你可以通过输入一个正整数列表和列表的长度来调用该函数。例如：

lst = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
n = len(lst)
print("最大素数为:", maximum_prime(n, lst))

输出结果为：

最大素数为: 29

给定n（n≤100）个正整数，所有正整数均≤1000000；求其中所有素数的和。

### 回答1：
题目：给一个$n$（$n\geq100$）个正整数，所有正整数均$\geq1000000$；求其中所有素数的和。

解法：使用埃拉托斯特尼筛法（Sieve of Eratosthenes）筛选素数。先建立一个从$100$到$n$的整数数组，将其中所有的偶数都标记为合数，然后从$3$开始遍历数组中所有未标记的奇数，将它的所有倍数都标记为合数。最后将所有未被标记的数相加即为所求的所有素数之和。在对一些数进行标记的时候可以采用较快的方法，如先对部分小的质数进行标记，大的质数则使用Miller-Rabin测试进行判断，可以大大降低时间复杂度。

### 回答2：
题目分析：

本题需要给定n个正整数，找出其中的所有素数并求和。对于一道求素数的题目，一般使用筛法较好。

在本题中，素数即为质数，可以使用埃氏筛或欧拉筛进行求解。

代码实现：

本题中使用埃氏筛法进行求解。

先定义一个bool型数组isPrime用来表示每个数字是否是素数，初始化都为true。

接着从2开始遍历到n，如果i为质数，则把i的倍数全部标记为false，表示非质数。

最后再次遍历整个数组，将isPrime等于true的所有数字相加即为所求。

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxN = 1e6+10;
bool isPrime[maxN];
int nums[maxN], n, sum;

void primeSum() {
    memset(isPrime, true, sizeof(isPrime));  //初始化所有数字为素数
    for(int i = 2; i <= maxN; i++) {
        if(isPrime[i]) {
            for(int j = i * 2; j <= maxN; j += i)
                isPrime[j] = false; // 标记i的倍数都不是素数
        }
    }
    for(int i = 1; i <= n; i++) {
        if(isPrime[nums[i]])
            sum += nums[i];
    }
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> nums[i];
    primeSum();
    cout << sum << endl;
    return 0;
}

时间复杂度：

本题中使用的是埃氏筛法，时间复杂度为O(n* log(log(n)))。其中log(log(n))为计算n以内质数个数的代价。

参考资料：

https://www.luogu.com.cn/problem/SP59

https://www.cnblogs.com/-Ackerman/p/13296338.html

### 回答3：
首先需要明确素数的定义，素数是指只能被1和本身整除的自然数，即除了1和本身以外没有其它因数的自然数。因此，判断一个数是否为素数的方法是从2到这个数的平方根之间，依次用这个数去除2到它的平方根之间的所有自然数，如果都不能被整除，则这个数为素数。

在给定n个正整数中寻找素数，我们可以逐个判断每个数是否为素数，并将素数累加起来求和。具体操作可以采用双重循环，外层循环遍历给定的n个正整数，内层循环判断这个数是否为素数。如果找到素数，则将它加入一个累加器中，最终得到的累加器即为给定n个正整数中所有素数的和。

需要注意的是，在内层循环中，应该先对待判断的数进行范围判断，如果这个数小于2，可以直接忽略；如果这个数等于2，那么它就是素数，可以直接加入累加器中；如果这个数是偶数，则也可以直接忽略，因为除了2以外，偶数都不是素数。

另外，可以通过一些优化操作来提高查找素数的效率，例如可以先将给定的n个正整数进行去重，或者使用一些已知的素数进行预处理，以减小内循环的遍历范围，提高程序效率。

综上所述，对于给定n个正整数，可以通过双重循环遍历每个数，用判断素数的方法进行判断，并将素数累加起来求和，即可得到所有素数的和。