计算数组中非质数元素的总和

来源: GeeksforGeeks

给定一个数组 arr[]，目标是计算并返回该数组中所有非质数元素的总和。
示例:

输入: arr[] = {1, 3, 7, 4, 9, 8}
输出: 22
数组中的非质数为{1, 4, 9, 8}，其和为 1 + 4 + 9 + 8 = 22
输入: arr[] = {11, 4, 10, 7}
输出: 14

解决方案: 初始化 sum = 0，然后遍历数组中的每个元素，如果当前元素不是质数，则将该元素加到 sum 中。最后，输出 sum 的值。为了高效地判断一个数是否为质数，可以使用埃拉托斯特尼筛法。
以下是不同编程语言实现此算法的代码示例:

C++ 示例

#include 
using namespace std;

int nonPrimeSum(int arr[], int n) {
    int max_val = *max_element(arr, arr + n);
    vector prime(max_val + 1, true);
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= max_val; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= max_val; i += p)
                prime[i] = false;
        }
    }
    int sum = 0;
    for (int i = 0; i         if (!prime[arr[i]])
            sum += arr[i];
    return sum;
}

int main() {
    int arr[] = {1, 3, 7, 4, 9, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout <    return 0;
}

Java 示例

import java.util.*;
class Solution {
    static int max_element(int arr[]) {
        int max_e = Integer.MIN_VALUE;
        for (int i = 0; i             max_e = Math.max(max_e, arr[i]);
        return max_e;
    }

    static int nonPrimeSum(int arr[], int n) {
        int max_val = max_element(arr);
        boolean prime[] = new boolean[max_val + 1];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int p = 2; p * p <= max_val; p++) {
            if (prime[p]) {
                for (int i = p * 2; i <= max_val; i += p)
                    prime[i] = false;
            }
        }
        int sum = 0;
        for (int i = 0; i             if (!prime[arr[i]])
                sum += arr[i];
        return sum;
    }

    public static void main(String args[]) {
        int arr[] = {1, 3, 7, 4, 9, 8};
        int n = arr.length;
        System.out.println(nonPrimeSum(arr, n));
    }
}

Python 示例

from math import sqrt

def nonPrimeSum(arr, n):
    max_val = max(arr)
    prime = [True] * (max_val + 1)
    prime[0] = prime[1] = False
    for p in range(2, int(sqrt(max_val)) + 1):
        if prime[p]:
            for i in range(p * 2, max_val + 1, p):
                prime[i] = False
    sum = 0
    for i in range(n):
        if not prime[arr[i]]:
            sum += arr[i]
    return sum

arr = [1, 3, 7, 4, 9, 8]
n = len(arr)
print(nonPrimeSum(arr, n))

C# 示例

using System;
class Program {
    static int max_element(int[] arr) {
        int max_e = int.MinValue;
        for (int i = 0; i             max_e = Math.Max(max_e, arr[i]);
        return max_e;
    }

    static int nonPrimeSum(int[] arr, int n) {
        int max_val = max_element(arr);
        bool[] prime = new bool[max_val + 1];
        for (int i = 0; i             prime[i] = true;
        prime[0] = prime[1] = false;
        for (int p = 2; p * p <= max_val; p++) {
            if (prime[p]) {
                for (int i = p * 2; i <= max_val; i += p)
                    prime[i] = false;
            }
        }
        int sum = 0;
        for (int i = 0; i             if (!prime[arr[i]])
                sum += arr[i];
        return sum;
    }

    public static void Main() {
        int[] arr = {1, 3, 7, 4, 9, 8};
        int n = arr.Length;
        Console.WriteLine(nonPrimeSum(arr, n));
    }
}

PHP 示例

function nonPrimeSum($arr, $n) {
    $max_val = max($arr);
    $prime = array_fill(0, $max_val + 1, true);
    $prime[0] = $prime[1] = false;
    for ($p = 2; $p * $p <= $max_val; $p++) {
        if ($prime[$p]) {
            for ($i = $p * 2; $i <= $max_val; $i += $p)
                $prime[$i] = false;
        }
    }
    $sum = 0;
    for ($i = 0; $i <$n; $i++)
        if (!$prime[$arr[$i]])
            $sum += $arr[$i];
    return $sum;
}

$arr = array(1, 3, 7, 4, 9, 8);
$n = count($arr);
echo nonPrimeSum($arr, $n);
?>

Javascript 示例

function max_element(arr) {
    let max_e = Number.MIN_VALUE;
    for (let i = 0; i         max_e = Math.max(max_e, arr[i]);
    return max_e;
}

function nonPrimeSum(arr, n) {
    let max_val = max_element(arr);
    let prime = new Array(max_val + 1).fill(true);
    prime[0] = prime[1] = false;
    for (let p = 2; p * p <= max_val; p++) {
        if (prime[p]) {
            for (let i = p * 2; i <= max_val; i += p)
                prime[i] = false;
        }
    }
    let sum = 0;
    for (let i = 0; i         if (!prime[arr[i]])
            sum += arr[i];
    return sum;
}

let arr = [1, 3, 7, 4, 9, 8];
let n = arr.length;
document.write(nonPrimeSum(arr, n));