العثور على أرقام رئيسية مع غربال eratosthenes (في الأصل: هل هناك طريقة أفضل لإعداد هذه الصفيف؟)

Question

ملحوظة: الإصدار 2، أدناه، يستخدم غربال eratosthenes. هناك العديد من الإجابات التي ساعدت في ما طلبته في الأصل. لقد اخترت غربال طريقة eratosthenes، ونفذها، وتغيير عنوان الأسئلة والعلامات بشكل مناسب. شكرا لكل من ساعد!

مقدمة

كتبت هذه الطريقة الصغيرة الفاخرة التي تولد مجموعة من كثافة 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;
}

إهتمامي

قلقي هو أن أقوم بإنشاء مجموعة كبيرة جدا بالنسبة للعدد النهائي للعناصر التي سترجعها الطريقة. المشكلة هي أنني لا أعرف وسيلة جيدة لتخمين عدد الأعداد الأولية بشكل صحيح أقل من رقم محدد.

ركز

هذه هي الطريقة التي يستخدم البرنامج الصفائف. هذا هو ما أريد تحسينه.

1. أقوم بإنشاء مجموعة مؤقتة كبيرة بما يكفي لعقد كل عدد أقل من الحد.
2. أقوم بإنشاء الأرقام الأولية، مع الحفاظ على عدد عدد الذين ولدتهم.
3. أقوم بإجراء مجموعة جديدة هذا هو البعد الصحيح لعقد الأرقام الرئيسية فقط.
4. أقوم بنسخ كل رقم رئيسي من الصفيف الضخم إلى مجموعة الأبعاد الصحيحة.
5. أعود مجموعة البعد الصحيح الذي يحمل فقط الأرقام الرئيسية التي قمت بإنشائها.

أسئلة

1. هل يمكنني نسخ الجزء كله (في وقت واحد) منtemp[] هذا له عناصر غير صفرة ل primes[]دون الحاجة إلى التكرار من خلال كل من المصفوفات ونسخ العناصر واحدة تلو الأخرى؟
2. هل هناك أي هياكل بيانات تتصرف مثل مجموعة من البدائيات التي يمكن أن تنمو مع إضافة عناصر، بدلا من طلب البعد عند إنشاء مثيل؟ ما هي عقوبة الأداء مقارنة باستخدام مجموعة من البدائيات؟

---

الإصدار 2 (بفضل جون skeet.):

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 (بفضل بول تومبلين) الذي يستخدم غربال 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;
}

Answer 1

تتمثل طريقتك في العثور على الأعداد الأولية، من خلال مقارنة كل عنصر من عنصري من مجموعة مع كل عامل ممكن غير فعال بشدة. يمكنك تحسينه بشكل كبير من خلال القيام غربال eratosthenes. على صفيف بأكملها مرة واحدة. إلى جانب القيام بمقارنات أقل بكثير، فإنه يستخدم أيضا إضافة بدلا من الانقسام. الانقسام هو الطريق أبطأ.

Answer 2

ArrayList<> غربال eratosthenes.

// 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;
}

Answer 3

يخترع ArrayList<Integer> ثم تحويل إلى int[] في نهايةالمطاف.

هناك مختلف الطرف الثالث IntList (إلخ) الطبقات حولها، ولكن ما لم تكن حقا قلق بشأن ضرب الملاكمة عدد قليل من الأعداد الصحيحة، وأنا لا تقلق بشأن ذلك.

يمكنك استخدام Arrays.copyOf لإنشاء مجموعة جديدة رغم ذلك. قد ترغب أيضا في تغيير حجمها من خلال مضاعفة الحجم في كل مرة تحتاج فيها، ثم تقليمها في النهاية. من شأنه أن يكون أساسا تحية ArrayList سلوك.

Answer 4

Algo باستخدام غربال eratosthenes

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;
}

صورة تصور ألغو أعلاه (خلايا اللون الرمادي تمثل العدد الأول. نظرا لأننا نعتبر جميع الأرقام كأعداد رئيسية كليا، فإن كل شيء هو Grid Gray في البداية.)

مصدر الصورة: ويكيميديا

Answer 5

سيكون أسهل الحل هو العودة بعض أعضاء إطار المجموعات بدلا من صفيف.

Answer 6

هل تستخدم Java 1.5؟ لماذا لا تعود List<Integer> واستخدام ArrayList<Integer>ب إذا كنت بحاجة إلى إعادة int[], ، يمكنك أن تفعل ذلك عن طريق تحويل القائمة إلى int[] في نهاية المعالجة.

Answer 7

كما يشير بولومبلين، هناك خوارزميات أفضل.

ولكن الحفاظ على ما لديك، وافتراض كائن كل نتيجة كبير جدا:

أنت فقط تضفي فقط على الصفيف. لذلك، استخدم مجموعة صغيرة نسبيا []. عند الاستخدام الكامل إلحاق به إلى قائمة وإنشاء بديل. في النهاية نسخها في صفيف بحجم صحيح.

بدلا من ذلك، تخمين حجم مجموعة int []. إذا كان صغيرا جدا، فاستبدل عن طريق int [] بحجم جزء أكبر من حجم الصفيف الحالي. سيظل أداء هذا الأمر من ذلك يتناسب مع الحجم. (تمت مناقشة هذا لفترة وجيزة في بودكاست Stackoverflow الأخير.)

Answer 8

الآن بعد أن حصلت على غربال أساسي في المكان، لاحظ أن الحلقة الداخلية تحتاج فقط إلى الاستمرار حتى temp[i]*temp[i] > prime.

Answer 9

لدي تنفيذ فعال حقا:

1. نحن لا نبقي الأرقام حتى، وبالتالي خفض استخدام الذاكرة.
2. نحن نستخدم BitSet, تتطلب قليلا فقط لكل عدد.
3. نقدر الحد العلوي للعدد من الأعداد الأولية على الفاصل الزمني، وبالتالي يمكننا ضبط initialCapacity للمجموعة بشكل مناسب.
4. نحن لا ننفذ أي نوع من الانقسام في الحلقات.

إليك الرمز:

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;
}

Answer 10

إعادة هيكلة الكود الخاص بك. قم بإلقاء الصفيف المؤقت، وبدلا من ذلك اكتب الوظيفة التي تختبر فقط عددا صحيحا. سيكون بسرعة معقولة، لأنك تستخدم الأنواع الأصلية فقط. ثم يمكنك، على سبيل المثال، حلقة وبناء قائمة بالأعداد الصحيحة التي هي رئيسية، قبل تحويل ذلك أخيرا إلى صفيف للعودة.

Answer 11

انتهيت أخيرا من البرنامج هو غربال محسن

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;
}

Answer 12

لست متأكدا مما إذا كان هذا سيجهح وضعك ولكن يمكنك إلقاء نظرة على نهجي. أنا استخدمت الألغام باستخدام غربال eratosthenes..

  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;
    }

إضافة تعليق لكل خطوات تم توضيحها في ويكيبيديا

Answer 13

لقد قمت باستخدام Hashmap ووجدها بسيطة للغاية

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);
                    }
                }

            }
        }

    }

}

أعتقد أن هذا فعال

Answer 14

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;
            }
        }
    }