العثور على جميع الأعداد الأولية في نطاق معين

Question

أنا أكتب برنامج Java هذا الذي يجد جميع الأعداد الأولية بين نطاق معين.نظرًا لأنني أتعامل مع أرقام كبيرة حقًا، يبدو أن الكود الخاص بي ليس بالسرعة الكافية ويعطيني خطأً في الوقت.هذا هو الكود الخاص بي، هل يعرف أحد كيفية جعله أسرع؟شكرًا.

import java.util.*;
public class primes2 
{   
    private static Scanner streamReader = new Scanner(System.in);
    public static void main(String[] args)
    {
        int xrange = streamReader.nextInt(); 
        int zrange = streamReader.nextInt();
        for (int checks = xrange; checks <= zrange; checks++)
        {
            boolean[] checkForPrime = Primes(1000000);
            if (checkForPrime[checks])
            {
                System.out.println(checks);
            }
        }
    }
    public static boolean[] Primes(int n)
    {
        boolean[] isPrime = new boolean[n + 1];
        if (n >= 2)
            isPrime[2] = true;
        for (int i = 3; i <= n; i += 2)
            isPrime[i] = true;
        for (int i = 3, end = sqrt(n); i <= end; i += 2)
        {
            if (isPrime[i]) 
            {
                for (int j = i * 3; j <= n; j += i << 1)
                    isPrime[j] = false;
            }
        }
        return isPrime;
    }
    public static int sqrt(int x)
    {
        int y = 0;
        for (int i = 15; i >= 0; i--) 
        {
            y |= 1 << i;
            if (y > 46340 || y * y > x)
                y ^= 1 << i;
        }
        return y;
        }
}

Answer 1

سوف تحصل على ضخم التحسين فقط عن طريق تغيير هذا:

    for (int checks = xrange; checks <= zrange; checks++)
    {
        boolean[] checkForPrime = Primes(1000000);

الى هذا:

    boolean[] checkForPrime = Primes(1000000);
    for (int checks = xrange; checks <= zrange; checks++)
    {

يقوم الكود الحالي الخاص بك بإعادة إنشاء المنخل zrange - xrange + 1 مرات، ولكنك في الواقع تحتاج إلى إنشائه مرة واحدة فقط.

Answer 2

المشكلة الواضحة هي أنك تقوم بحسوس الأعداد الأولية حتى 1000000 مرة أخرى (Zrange - Xrange Times).آخر هو أنه لا تحتاج إلى حساب الأعداد الأولية تصل إلى 1000000، فأنت بحاجة فقط إلى التحقق من الأعداد الأولية إلى Zrange، لذلك أنت تضيع الوقت عند زرج <1000000، والحصول على تجاوز سعة مخزن مؤقت عند Zrange> 1000000.

Answer 3

يمكنك أن تبدأ حلقتك الداخلية من i*i, ، أي.بدلاً من for (int j = i * 3; j <= n; j += i << 1) يمكنك كتابة for (int j = i * i; j <= n; j += i << 1) لتسريع طفيف.

أيضا، عليك أن تكون على يقين من أن الخاص بك zrange ليس أكبر من 1000000.

لو xrange أكبر بكثير من sqrt(zrange), ، يمكنك أيضًا تقسيم مجموعة الغربال الخاصة بك إلى قسمين، مقابل غربال الأوفست مخطط.سوف تمتد المجموعة السفلية من 2 إلى sqrt(zrange).سوف يمتد الجزء العلوي من xrange ل zrange.عندما تقوم بغربلة المصفوفة السفلية، حيث يتم التعرف على كل عدد أولي جديد بها، داخل الحلقة الداخلية، بالإضافة إلى وضع علامة على المصفوفة السفلية حتى نهايتها، قم أيضًا بغربلة المصفوفة العلوية.سيكون عليك حساب إزاحة البداية لكل عدد أولي i, ، واستخدم نفس الخطوة 2*i كما تفعل للنصف السفلي.إذا كان نطاقك أوسع من عدد قليل من الأعداد الأولية، فستحصل على ميزة السرعة (وإلا فإن التقسيم التجريبي على الاحتمالات سيكون كافيًا).

شيء آخر يجب تجربته هو، إذا كان متساويًا > 2 ليست أعدادًا أولية على أي حال، فلماذا تمثلها في المصفوفة وتضيع نصف المساحة؟يمكنك علاج كل منهما i باعتباره يمثل رقمًا فرديًا، 2*i+1, ، هكذا ضغط الصفيف الخاص بك في النصف.

آخر خدعة بسيطة هي إزالة مضاعفات الرقم 3 مقدماً وكذلك عن طريق وضع العلامات ON ليس فقط odds (أي.كوبريم مع 2)، بواسطة { ... i+=2; ...}, ، ولكن فقط coprimes مع 2 و 3, ، بواسطة { ... i+=2; ... i+=4; ... } بدلاً من.وكذلك عند وضع العلامات OFF مضاعفات الأعداد الأولية > 3, ، يستخدم { ... j+=2*i; ... j+=4i; ...} أيضاً.على سبيل المثال، في 5*5, 5*7, 5*9, 5*11, ... لا تحتاج لوضع علامة OFF 5*9, ، إذا لم يكن هناك متعددة 3 وقد تميز ON في المقام الأول.