寻找数字与总理的筛埃拉托塞尼(最初：是否有更好的办法准备这阵?)

https://stackoverflow.com/questions/586284

06-09-2019
|

题

注： 2版，以下，使用筛埃拉托塞尼.有几个答案，帮助有什么我最初的问。我有选择的筛埃拉托塞尼的方法，执行它，并且改变了该问题标题和标签适当。感谢大家的帮助!

介绍

我写了这个花哨一点的方法，产生一系列int含的总数少于规定上限。它工作得很好，但是我有一个问题。

该方法

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    int [] primes = new int [index];
    while(--index >= 0) {
        primes [index] = temp [index];
    }
    return primes;
}

我担心的

我担心的是，我在创建一个数组，远远过大的最终数量的元素的方法将返回。麻烦的是，我不知道一个很好的方式来猜的数量总人数少于规定的数量。

重点

这是怎样的程序使用的阵列。这就是我想要的改善。

我创建了一个临时阵列足够大，以保持每个数字不到的限制。
我产生的总理数量，同时保持计数的多少我有产生的。
我让一个新的阵列的，是正确的维持只是总理数字。
我复制每一个总数从巨大的阵阵的正确的尺度。
我回来的系列正确的维持有只是总理号码我产生的。

的问题

我可以复制的整个区块(一次)的 temp[] 有零元素 primes[] 没有必要迭代过这两个阵和复制的元素一个一个的?
是否有任何数据结构表现得像一系列原语这可以成长为因素相加，而不是要求一个尺寸在实例?什么是的性能的惩罚相比使用一系列原语?

第2版(多谢乔恩的飞碟):

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    return Arrays.copyOfRange(temp, 0, index);
}

3版(谢谢保罗Tomblin)其使用筛Erastosthenes:

private static int [] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) {
        if (!isComposite [i]) {
            for (int j = i; i * j <= max; j++) {
                isComposite [i*j] = true;
            }
        }
    }
    int numPrimes = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) numPrimes++;
    }
    int [] primes = new int [numPrimes];
    int index = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) primes [index++] = i;
    }
    return primes;
}

解决方案

你的方法寻找素，通过比较每一个元件阵列与每一个可能的因素是令人发指的效率低下。你可以提高它巨大的通过做一个筛埃拉托塞尼在整个阵列一次。除了做远比较少，它也使用外而不是分裂。司法速度较慢。

其他提示

`ArrayList<>` 筛埃拉托塞尼

// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
    final int numPrimes = countPrimesUpperBound(limit);
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    boolean [] isComposite    = new boolean [limit];   // all false
    final int sqrtLimit       = (int)Math.sqrt(limit); // floor
    for (int i = 2; i <= sqrtLimit; i++) {
        if (!isComposite [i]) {
            primes.add(i);
            for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                isComposite [j] = true;
        }
    }
    for (int i = sqrtLimit + 1; i < limit; i++)
        if (!isComposite [i])
            primes.add(i);
    return primes;
}

公式对上限的数量的数少于或等于 max (见 wolfram.com):

static int countPrimesUpperBound(int max) {
    return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}

创建一个 ArrayList<Integer> 然后换一个 int[] 在结束。

有各种不同的第3次方 IntList (等等)的课程周围，但是除非你是真的担心的是打拳击几整数，我不会担心它。

你可以用 Arrays.copyOf 创建新的阵虽然。你可能还需要调整，通过增加一倍大小的每个时候需要，然后trim的末尾。这将基本上可以模仿 ArrayList 行为。

Algo使用筛埃拉托塞尼

public static List<Integer> findPrimes(int limit) {

    List<Integer> list = new ArrayList<>();

    boolean [] isComposite = new boolean [limit + 1]; // limit + 1 because we won't use '0'th index of the array
    isComposite[1] = true;

    // Mark all composite numbers
    for (int i = 2; i <= limit; i++) {
        if (!isComposite[i]) {
            // 'i' is a prime number
            list.add(i);
            int multiple = 2;
            while (i * multiple <= limit) {
                isComposite [i * multiple] = true;
                multiple++;
            }
        }
    }

    return list;
}

图像，描绘了上述algo(灰色单元格表示质数。因为我们考虑所有数字为总理的数字最初，整个电网是灰色的开始。)

enter image description here

图片来源：维基

最简单的解决办法是返回的一些成员集合框架而不是一个阵列。

您使用的是Java1.5?为什么不回 List<Integer> 和使用 ArrayList<Integer>?如果你需要返回一个 int[], 您可以做它通过转换列表 int[] 在结束处理。

正如保罗Tomblin指出，有更好的算法。

但是跟你有什么，假设一对象每结果太大：

你只是没有追加到阵列。因此，使用相对较小的int[]array.当它的充分利用追加的一个列表并创建一个替代品。在结束复制成一个正确的中小型阵列。

或者，你猜的大小int[]array.如果太小，替换由一个int[]小一部分大于目前列的大小。表现的开销的，这将仍然是成比例的大小。(这是简要讨论在最近的一个计算器的播客。)

现在，你已经有了一个基本的筛在的地方，注意到内部循环只需要继续直到 temp[i]*temp[i] > prime.

我有一个真正有效的执行：

我们不保持甚至数字，因此减少一半的存储器的使用。
我们使用 BitSet, 仅需要一位每数。
我们估计上限数量的数月的时间间隔，因此，我们可以设置 initialCapacity 阵列适当。
我们不执行任何种类的划分的循环。

这里的代码:

public ArrayList<Integer> sieve(int n) {
    int upperBound = (int) (1.25506 * n / Math.log(n));
    ArrayList<Integer> result = new ArrayList<Integer>(upperBound);
    if (n >= 2)
        result.add(2);

    int size = (n - 1) / 2;
    BitSet bs = new BitSet(size);

    int i = 0;
    while (i < size) {
        int p = 3 + 2 * i;
        result.add(p);

        for (int j = i + p; j < size; j += p)
            bs.set(j);

        i = bs.nextClearBit(i + 1);
    }

    return result;
}

重组你的代码。扔出临时阵列，而是写信的功能，只是总理测试一个整数。这将是相当快的，因为你只使用本地的类型。然后你可以，例如，循环并建立一个整数列表，总理之前，最后转到一系列返回。

我最后完成的程序这是一个优化的筛

public static int[] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    LinkedList<Integer> Primes = new LinkedList<>(); //linkedlist so not have to iterate 2 times
    int sqrt = (int) Math.sqrt(max); //end at the square root
    for (int i = 2; i <= sqrt; i++) {
        if (!isComposite[i]) {
            int s = i*i; //start from the prime's square
            while (s <= max) {
                isComposite[s] = true; //oh no its a not prime
                s+=i;
            }
        }
    }
    for(int i = 2; i < max; i++){
        if(!isComposite[i]){
            Primes.add(i);
        }
    }
    int[] result = new int[Primes.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = Primes.get(i);
    }
    return result;
}

不知道，如果这套你的情况，但是你可以看一下我的做法。我用我的使用筛埃拉托塞尼.

  public static List<Integer> sieves(int n) {
        Map<Integer,Boolean> numbers = new LinkedHashMap<>();

        List<Integer> primes = new ArrayList<>();

        //First generate a list of integers from 2 to 30
        for(int i=2; i<n;i++){
            numbers.put(i,true);
        }

        for(int i : numbers.keySet()){
            /**
             * The first number in the list is 2; cross out every 2nd number in the list after 2 by 
             * counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):
             * 
             * The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by 
             * counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):
             * The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every
             * 7th number in the list after 7, but they are all already crossed out at this point,
             * as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. 
             * The numbers not crossed out at this point in the list are all the prime numbers below 30:
             */
            if(numbers.get(i)){
                for(int j = i+i; j<n; j+=i) {
                    numbers.put(j,false);
                }
            }
        }


        for(int i : numbers.keySet()){
            for(int j = i+i; j<n && numbers.get(i); j+=i) {
                numbers.put(j,false);
            }
        }

        for(int i : numbers.keySet()){
           if(numbers.get(i)) {
               primes.add(i);
           }
        }
        return primes;
    }

加评论的每个步骤已经说明在维基百科

我已经做了使用哈希并确认它非常简单

import java.util.HashMap;
import java.util.Map;

/*Using Algorithms such as sieve of Eratosthanas */

public class PrimeNumber {

    public static void main(String[] args) {

        int prime = 15;
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        hashMap.put(0, 0);
        hashMap.put(1, 0);
        for (int i = 2; i <= prime; i++) {

            hashMap.put(i, 1);// Assuming all numbers are prime
        }

        printPrimeNumberEratoshanas(hashMap, prime);

    }

    private static void printPrimeNumberEratoshanas(HashMap<Integer, Integer> hashMap, int prime) {

        System.out.println("Printing prime numbers upto" + prime + ".....");
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue().equals(1)) {
                System.out.println(entry.getKey());
                for (int j = entry.getKey(); j < prime; j++) {
                    for (int k = j; k * j <= prime; k++) {
                        hashMap.put(j * k, 0);
                    }
                }

            }
        }

    }

}

认为这是有效的

public static void primes(int n) {
        boolean[] lista = new boolean[n+1];
        for (int i=2;i<lista.length;i++) {
            if (lista[i]==false) {
                System.out.print(i + " ");
            }
            for (int j=i+i;j<lista.length;j+=i) {
                lista[j]=true;
            }
        }
    }

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow

寻找数字与总理的筛埃拉托塞尼(最初：是否有更好的办法准备这阵?)

介绍

该方法

我担心的

重点

的问题

ArrayList<> 筛埃拉托塞尼

`ArrayList<>` 筛埃拉托塞尼