java - 计算非质数

问题描述

我想创建一个从 int 数组返回非素数数量的方法。

我用来标记数组中素数的方法如下所示（这部分不需要任何更改）：

public static int markNonePrimeNumbers(int[] array) {
        createInitialArray(100);
        for (int j = 2; j < array.length; j++) {
            for (int i = j * 2; i < array.length; i += j) {
                array[i] = 0;
            }
        }

我想修改它，以便它可以返回 array[i] = 0 的数量并计算它。

我通过添加一个 HashMap 走了这么远：

public static int[] markNonePrimeNumbers(int[] array) {
    createInitialArray(100);
    for (int j = 2; j < array.length; j++) {
        for (int i = j * 2; i < array.length; i += j) {
            array[i] = 0;
        }
    }
    Map<Integer, Integer> map = new HashMap<>();
    for (int key : array) {
        if (map.containsKey(key)) {
            int occurrence = map.get(key);
            occurrence++;
            map.put(key, occurrence);
        } else {
            map.put(key, 0);
        }
    }
    for (Integer key : map.keySet()) {
        int occurrence = map.get(key);
        System.out.println(occurrence);
    }

一般来说，我很接近，但我不知道如何从 Map 中删除所有高于 1 的索引。它已经计算了第一个索引上 0 的数量。

标签： javaarrayshashmapsieve-of-eratosthenes

做到这一点的最佳方法之一是保留一个运行的素数列表，然后检查该列表。第一部分是驱动程序代码，因此无需解释。

        int[] array = new int[] { 1,19, 2, 3, 4, 57, 10, 7, 11,
                13, 17, 16 };
        List<Integer> nonPrimes = new ArrayList<>();
        for (int c : array) {
            if (!isPrime(c)) {
                nonPrimes.add(c);
            }
        }
        System.out.println(nonPrimes);

这是主要查找方法的开始。要点如下：

它使用 aLinkedHashSet来存储素数。
一个。它维持秩序。
湾。允许快速查找特定值
它找到提交值之前的所有素数并存储它们。仅当提交的值大于记录的最后一个素数时才会这样做。
随后的候选素数从记录的最后一个素数 + 2 开始。由于 2 之后的所有素数都是奇数，因此这也保证是下一个奇数。候选人加 2 以跳过偶数。
为了检测候选者是否是素数，除以先前记录的素数（但仅限于square root候选者）。

    static Set<Integer> primes = new LinkedHashSet<>() {
        {   // seed the first two primes.
            add(2);
            add(3);
        }
    };

    // last recorded prime
    static int lastPrime = 3;

    public static boolean isPrime(int val) {
        for (int candidate = lastPrime+2; candidate <= val; candidate += 2) {
           int max = (int)(Math.sqrt(candidate)) + 1;
            for (int p : primes) {
                // if candidate is divisible by any prime, then discontinue
                // testing and move on to next candidate via outer loop
                if (candidate % p == 0) {
                    break;
                }
                // if the limit has been reached, then a prime has been
                // found, so add to list of primes and continue with
                // next candidate.  Only check up tot he square root of the candidate.
                if (p >= max) {
                    // add new found prime to list
                    primes.add(candidate);
                    lastPrime = candidate;
                    break;
                }
            }
        }
        // Now check the newly built (if required) hash set to see if the passed value
        // is in the list.
        return primes.contains(val);
    }

java - 计算非质数

问题描述

解决方案

推荐阅读