مكدس الفائض عند حساب الرقم الرئيسي 10،001 في جافا

Question

أنا أفعل مشكلة 7 من مشروع أولر. ما يفترض أن أفعله هو حساب 10،001^شارع رقم اولي. (العدد الرئيسي هو عدد صحيح أكبر من العدد القابل للقسمة وحدها فقط.)

هذا هو برنامجي الحالي:

public class Problem7 {
    public static void main(String args[]) {
        long numberOfPrimes = 0;
        long number = 2;

        while (numberOfPrimes < 10001) {
            if (isPrime(number)) {
                numberOfPrimes++;
            }
            number++;
        }
        System.out.println("10001st prime: " + number);
    }

    public static boolean isPrime(long N) {
        if (N <= 1)
            return false;
        else
            return Prime(N, N - 1);
    }

    public static boolean Prime(long X, long Y) {
        if (Y == 1)
            return true;
        else if (X % Y == 0)
            return false;
        else
            return Prime(X, Y - 1);
    }
}

إنه يعمل بشكل جيد مع العثور على 100^ذ العدد الرئيسي ، ولكن يعمل مع مدخلات كبيرة جدا (مثل 10،001) يؤدي إلى تجاوز سعة المكدس. لماذا ، وكيف يمكنني إصلاح هذا؟

Answer 1

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

Answer 2

يستخدم "غربال eratosthenes"

مصدر جافا:

public class Main {
    public static void main(String args []){
        long numberOfPrimes = 0;
        int number = 1;
        int maxLimit = 10000000;
        boolean[] sieve = new boolean[maxLimit];
        for ( int i = 2; i < maxLimit; i++ ) {
            if ( sieve[i] == true ) continue;

            numberOfPrimes++;

            if ( numberOfPrimes == 10001 ) {
                number = i;
                break;
            }

            for ( int j = i+i; j < maxLimit; j += i )
                sieve[j] = true;
        }
        System.out.println("10001st prime: "+ number);
    }
}

Answer 3

يجب عليك حفظ جميع الأرقام الأولية التي حصلت عليها حتى الآن في قائمة البحث ، لذلك ستحقق مما إذا كان الرقم مقسومًا على الأرقام من تلك القائمة. إذا لم يكن هذا هو رقم رئيسي - انتقل إلى إضافته إلى القائمة.
فكرة أخرى هي استبدال number++; مع number += 2; والبدء في التحقق من 3 بمجرد الأرقام باستثناء 2 ليست بارزة.

Answer 4

لقد حللت هذه المشكلة مؤخرًا. أود أن أقترح توليد الأعداد الأولية مع غربال eratosthenes, ، قل كل الأعداد الأولية <1 مليون. إنها ليست خوارزمية صلبة للتنفيذ ، وهي سريعة إلى حد ما لعدد الأعداد الأولية التي تحتاجها.

Answer 5

ستقوم المجمعون ببعض اللغات (على سبيل المثال ، العديد من اللغات الوظيفية وشبه وظيفية مثل LISP) إلى تحويل عودية الذيل كما استخدمت في التكرار ، ولكن (على ما يبدو) لم يتم قيام برنامج التحويل البرمجي Java بذلك من أجلك. نتيجة لذلك ، تستخدم كل مكالمة متكررة مساحة المكدس ، وفي النهاية تنفد وتفيض المكدس.

بالطبع ، بالنسبة لمعظم الأغراض ، تريد استخدام خوارزمية مختلفة - ما تستخدمه الآن مروع للغاية مع تقدم هذه الأشياء. على الأقل ، تحتاج فقط إلى التحقق من الأرقام الفردية حتى الجذر التربيعي للرقم الذي تختبره ...

Answer 6

استراتيجيتك لاختبار Prime هي التحقق من قابليتها للقسمة مع كل رقم طبيعي أصغر.

إذا قمت بتحويل استراتيجيتك إلى اختبار القسمة مع كل برايم أصغر ، فسوف توفر الكثير من الحساب.

Answer 7

import java.util.*;

public class LargestPrime {
    public static boolean isPrime(long s) {
        for(long i = 2; i < s; i++) {
            if((s % i) == 0) return false;                   
        }
        return true;
    }

    public static void main(String[] args) {
        LargestPrime p = new LargestPrime();
        LinkedList<Long> arr = new LinkedList<Long>();
        for(long j = 2; j <= 999999; j++) {

            if(isPrime(j)) arr.add(j);

        }
        // System.out.println("List of Prime Number are: "+ arr);
        long t = arr.get(10001);

        System.out.println("The Prime Number At 10001st position: " + t);
    }
}

Answer 8

لحل هذا بشكل عام ، سيتعين عليك التبديل من حل عودي إلى حل تكراري. (يمكن التعبير عن كل خوارزمية متكررة بشكل متكرر أيضًا.)

نظرًا لأن Prime Prime عودية ، فسيكون هناك دائمًا حد للنظام على عدد المرات التي يمكن أن تسميها نفسها.

ومع ذلك ، قد يكون لديك ذاكرة كافية على نظامك للوصول إلى 10001. تسمح لك Java بتعيين أقصى قدر من الذاكرة (المكدس ، الكومة ، إلخ) التي يستخدمها VM. قم بزيادة رقم ذاكرة المكدس ، وربما ستكون قادرًا على تحقيق ذلك. انظر هذه الصفحة

http://docs.sun.com/source/817-2180-10/pt_chap5.html

لبعض خيارات Java VM.

Answer 9

يمكنك دائما استخدام رابين ميلر اختبار البدائية. إنها خوارزمية سهلة للغاية وسريعة للغاية ، على الرغم من أن فهم كيفية عملها أكثر صرامة.

Answer 10

package problems;

public class P_7 {
    /**
     * @param args
     */
    public static boolean prime(double num)
    {
        double x=2;
        double limit=(int) ((num/2)-(num/2)%1);
        while(x<=limit)
        {
            if(num%x==0)
                return false;
            x++;
        }
        return true;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int i=1;
        int j=3;
        while(i<=10000)
        {
            if(prime(j))
            {
                System.out.println(i);
                i++;
                System.out.println(j);
            }
            j++;
        }
    }
}

هذه إجابتي العاملة.

Answer 11

في C ... يمكنك عمل نسخة أقصر ، ولكن أيا كان: D ..

#include <stdio.h>
#include <stdlib.h>

prost_br(int p)
{
    int br=0;

    for(int i=2;i*i<=p;i++)
    if(p%i==0)
    br++;

    if(br==0)
    return 1;
    return 0;
}

int main()
{
    long i=1;
    int br=0;
FILE *a;

a=fopen("10001_prst_numbers.txt","w");
if(a==NULL){printf("\nError!\a\n"); exit(1);}

    while(br!=10001)
    {
        i++;
        if(prost_br(i))
        {
            br++;
            fprintf(a,"%d ",i);
        }

    }
    char s[]={"10001th prime number is: "};
fprintf(a,"\n%s %d",s,i);
fprintf(stdout,"\n10001th prime number is: %d\n\a",i);

fclose(a);
system("Pause");
}

Answer 12

تكمن المشكلة في متكرر يعرف Prime(X,Y) وظيفة ، ولكن أيضا في الخوارزمية المستخدمة. لا يوجد سوى الكثير من العودية عمق يمكن أن تستوعب آلية استدعاء الوظيفة في Java قبل استنفاد مكدس الاتصال ، مما تسبب في خطأ "Fluslow".

يكفي اختبار التقسيم مقابل جميع الأرقام أسفل الجذر التربيعي للرقم الذي يتم اختباره. من حيث رمز البروتوكول الاختياري ، هذا يعني البدء من Prime(N,N-1), ، ولكن بالأحرى من Prime( N, floor( sqrt( N+1)) ). قد يكون هذا التغيير وحده كافياً لمنع الخطأ في هذه المهمة المحددة ، حيث سيتغير عمق التكرار من 10000 إلى 100 فقط.

مشاكل الخوارزمية تبدأ فقط هناك. ال Prime(X,Y) تعداد الرمز تحت, ، وبالتالي اختبار الرقم بأرقام أكبر أولاً. ولكن تم العثور على عوامل أصغر في كثير من الأحيان ؛ يجب أن يتم العد من أصغر عامل ممكن ، 2 (الذي تمت مواجهته بنسبة 50 ٪ من الأرقام) ، فوق إلى sqrt رقم المرشح. يجب إعادة كتابة الوظيفة على أنها بسيطة while حلقة في هذه الفرصة أيضًا.

التحسن السهل والواضح هو تجاهل الأرقام الزوجية تمامًا. من المعروف أن تكون بارزة. جميع evens الأخرى ليست كذلك. هذا يعني بدء الحلقة من numberOfPrimes = 1; number = 3; والعد من قبل number += 2 لتعداد الأرقام الفردية فقط ، وجود isPrime(N) اختبار قابليتها للقسمة فقط من قبل غريب الأرقام كذلك ، في أ while حلقة تبدأ مع X = 3, ، اختبار ل N % X والعد من قبل X += 2.

أو في كود مزيف (في الواقع ، هاسكل) ، الرمز الأصلي هو

main = print ([n | n<-[2..], isPrime(n)] !! 10000)  where   
  isPrime(n) = _Prime(n-1)  where
      _Prime(y) = y==1 || (rem n y > 0 && _Prime(y-1)) 
  -- 100:0.50s 200:2.57s 300:6.80s 10000:(projected:8.5h)
  --       n^2.4       n^2.4

الإصلاح المقترح:

main = print ((2:[n | n<-[3,5..], isOddPrime(n)]) !! 10000)  where   
  isOddPrime(n) = _Prime(3)  where
         _Prime(y) = (y*y) > n || (rem n y > 0 && _Prime(y+2)) 
  -- 100:0.02s 200:0.03s 300:0.04s 5000:3.02s 10000:8.60s
  --                                       n^1.5

التوقيتات المعروضة مخصصة للرمز غير المجبر في GHCI (على جهاز كمبيوتر محمول بطيء). أوامر النمو المحلية التجريبية تؤخذ على أنها log(t2/t1) / log(n2/n1). حتى أسرع هو اختبار الأعداد الأولية ، وليس بالأرقام الفردية.

بالمناسبة، الرمز الأصلي لا يطبع الذروة 10001 ، ولكن الرقم أعلاه.

Answer 13

بروغ الطبقة العامة {

public int nthPrime(int nth) {
    int ctr = 0;
    int num = 0;
    int x = 2;
    int infinite = 15;          // initial value good for 6 prime values
    while(x < infinite) {
        boolean isPrime = true; 
        for(int i = 2; i <= x / 2; i++) {
            if(x % i == 0) {
                isPrime = false;
            }
        }
        if(isPrime) {
            System.out.println(x);  // optional
            ctr++;
            if(ctr == nth) {
                num = x;
                break;
            }
        }
        x++;
        if(x == infinite) {     // for bigger nth requested prime value
            infinite++;     
        }
    }
    return num;
}

public static void main(String[] args) {
    int ans = new progs().nthPrime(10001);
    System.out.println("nth prime number is " + ans);
}

}