当前位置： 文江博客话题详情

Java计算第10001个素数时堆栈溢出

发布于 2024-08-26 11:09:40 字数 900 浏览 10 评论 0原文

我正在做欧拉计划的第七题。我应该做的是计算第 10,001st 个素数。 （素数是大于 1 的整数，只能被它本身和 1 整除。）

这是我当前的程序：

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）会导致堆栈溢出。我该如何修复它？

原文

I am doing problem 7 of Project Euler. What I am supposed to do is calculate the 10,001st prime number. (A prime number is an integer greater than one that is only divisible by itself and one.)

Here is my current program:

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

It works okay with finding, say the 100th prime number, but running with very large inputs (such as 10,001) results in stack overflow. How do I fix it?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（14）

独行侠 2024-09-02 11:09:40

我认为问题在于您递归地调用 Prime 来确定数字是否为素数。因此，要确定数字 1000 是否为素数，您需要递归调用 Prime 1000 次。每次递归调用都需要将数据保存在堆栈上。堆栈只有这么大，因此最终您会耗尽堆栈上的空间来继续进行递归调用。尝试使用迭代解决方案而不是递归解决方案。

I think the problem is that you're recursively calling Prime to determine if a number is prime or not. So, to determine whether the number 1000 is prime or not, you're calling Prime 1000 times recursively. Each recursive call requires data to be kept on the stack. The stack is only so large, so eventually you run out of room on the stack to keep making recursive calls. Try using an iterative solution instead of a recursive solution.

回复 原文
梦中的蝴蝶 2024-09-02 11:09:40

使用“埃拉托斯特尼筛法”

Java源代码：

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

Use "Sieve of Eratosthenes"

Java source:

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);
    }
}
回复 原文
御弟哥哥 2024-09-02 11:09:40

您应该将到目前为止获得的所有素数保存到查找列表中，因此您将检查该数字是否除以该列表中的数字。如果不是质数 - 将其添加到列表中。
另一个想法是将 number++; 替换为 number += 2; 并从 3 开始检查，只要偶数（除外） 2 不是素数。

You should save all the prime numbers you got so far into a look up list therefore you'll be checking if the number is divided by the numbers from that list. If not it's a prime number - go add it to the list.
Another idea is to replace number++; with number += 2; and start checking from 3 as soon as even numbers with exception for 2 are not prime.

回复 原文
烏雲後面有陽光 2024-09-02 11:09:40

我最近解决了这个问题。我建议使用 埃拉托斯特尼筛 生成素数，假设所有素数 < 100万。这不是一个很难实现的算法，而且对于您需要的素数数量而言，它的速度相当快。

I recently solved this problem. I'd suggest generating your primes with a Sieve of Eratosthenes, say all primes < 1 million. It's not a hard algorithm to implement, and it's fairly fast for the number of primes you need.

回复 原文
错々过的事 2024-09-02 11:09:40

某些语言的编译器（例如，许多函数式和半函数式语言，如 Lisp）会将尾递归转换为迭代，但（显然）Java 编译器不会为您执行此操作。结果，每个递归调用都使用堆栈空间，最终用完并且堆栈溢出。

当然，对于大多数目的，您想要使用不同的算法——随着这些事情的发展，您现在使用的算法非常糟糕。至少，您只需要检查奇数到您正在测试的数字的平方根......

Compilers for some languages (e.g. many functional and semi-functional languages like Lisp) will convert tail recursion like you've used into iteration, but (apparently) the Java compiler isn't doing that for you. As a result, every recursive call is using stack space, and eventually you run out and the stack overflows.

Of course, for most purposes, you want to use a different algorithm -- what you're using right now is pretty awful as these things go. At the very least, you only need to check odd numbers up to the square root of the number you're testing...

回复 原文
我的奇迹 2024-09-02 11:09:40

测试素数的策略是检查它与每个较小的自然数的整除性。

如果你改变你的策略来测试每一个较小的素数的整除性，你将节省大量的计算量。

Your strategy to test a prime is to check its divisibility with every smaller natural number.

If you shift your strategy to test for divisibility with just every smaller prime, you would save a whole lot of computation.

回复 原文
怀念你的温柔 2024-09-02 11:09:40
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);
    }
}

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);
    }
}
回复 原文
随波逐流 2024-09-02 11:09:40

一般来说，为了解决这个问题，您必须从递归解决方案切换到迭代解决方案。 （每个递归算法也可以迭代地表达。）

由于 Prime 函数是递归的，因此它可以调用自身的次数始终存在系统限制。

但是，您的系统上可能有足够的内存达到 10001。Java 允许您设置 VM 使用的最大内存量（堆栈、堆等）。增加堆栈内存数量，你可能就能做到。请参阅此页

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

用于某些 Java VM 选项。

To solve this in general, you're going to have to switch from a recursive solution to an iterative one. (Every recursive algorithm can be expressed iteratively, too.)

Since function Prime is recursive, there will always be a system limit on how many times it can call itself.

However, you may have enough memory on your system to reach 10001. Java allows you to set the maximum amount of memory (stack, heap, etc) that the VM uses. Increase the stack memory number, and you'll probably be able to make it. See this page

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

for some of the Java VM options.

回复 原文
筑梦 2024-09-02 11:09:40

您始终可以使用 Rabin-Miller 素性测试。这是一种非常容易实现的算法，而且速度非常快，尽管理解它的工作原理有点困难。

You could always use the Rabin-Miller primality test. It's a very easy to implement algorithm and very fast, though understanding how it works is a bit tougher.

回复 原文
落花随流水 2024-09-02 11:09:40
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++;
        }
    }
}

这是我的工作答案。

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

this is my working answer.

回复 原文
暗恋未遂 2024-09-02 11:09:40

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

In C... You can do shorter version, but whatever :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");
}
回复 原文
浮萍、无处依 2024-09-02 11:09:40

问题在于递归地定义的Prime(X,Y)函数，而且还在于所使用的算法。在调用堆栈耗尽之前，Java 的函数调用机制只能容纳这么多的递归深度，从而导致“堆栈溢出”错误。

测试所有低于所测试数字的平方根的数字的整除性就足够了。就操作代码而言，这意味着不是从 Prime(N,N-1) 开始，而是从 Prime( N, Floor( sqrt( N+1)) ) 开始代码>.仅此更改就足以防止此特定任务出现 SO 错误，因为递归深度将从 10000 更改为 100。

算法问题仅从这里开始。 Prime(X,Y) 代码向下计数，因此首先通过较大的数字来测试数字。但较小的因素被发现的频率要高得多。计数应从尽可能小的因子 2（50% 的数字都会遇到）开始，向上到 sqrt候选人编号。趁这个机会，该函数也应该被重写为一个简单的 while 循环。

下一个简单而明显的改进是完全忽略偶数。已知 2 是素数；所有其他事件都不是。这意味着从 numberOfPrimes = 1 开始循环； number = 3; 并按 number += 2 向上计数以仅枚举奇数，让 isPrime(N) 测试它们仅被 整除奇数也是如此，在以X = 3开始的while循环中，测试N % X并按<代码>X += 2。

或者在伪代码（实际上，Haskell）中，原始代码是

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 个素数，而是它上面的数字。

The problem lies in the recursively defined Prime(X,Y) function, but also in the algorithm used. There is only so much recursion depth that the function call mechanism of Java can accommodate before the call stack is exhausted, causing the "stack overflow" error.

It is enough to test for divisibility against all numbers below the square root of the number being tested. In terms of the OP code, that means starting not from Prime(N,N-1), but rather from Prime( N, floor( sqrt( N+1)) ). This change alone could be enough to prevent the SO error for this specific task, as the recursion depth will change from 10000 to just 100.

Algorithmic problems only start there. The Prime(X,Y) code counts down, thus testing the number by bigger numbers first. But smaller factors are found far more often; the counting should be done from the smallest possible factor, 2 (which is encountered for 50% of numbers), up to the sqrt of the candidate number. The function should be re-written as a simple while loop at this opportunity, too.

Next easy and obvious improvement is to ignore the even numbers altogether. 2 is known to be prime; all other evens are not. That means starting the loop from numberOfPrimes = 1; number = 3; and counting up by number += 2 to enumerate odd numbers only, having isPrime(N) test their divisibility only by the odd numbers as well, in a while loop starting with X = 3, testing for N % X and counting up by X += 2.

Or in pseudocode (actually, Haskell) , the original code is

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

the proposed fix:

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

Timings shown are for non-compiled code in GHCi (on a slow laptop). Empirical local orders of growth taken as log(t2/t1) / log(n2/n1). Even faster is testing by primes, and not by odd numbers.

btw, the original code prints not the 10001st prime, but the number above it.

回复 原文
盛夏尉蓝 2024-09-02 11:09:40

公开课程序 {

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

}

public class progs {

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

}

回复 原文
一向肩并 2024-09-02 11:09:40
import java.util.*;
public class Main
{
    public static void main(String[] args) {
        int n = 1000;
        List<Integer> list = new ArrayList<>();
        list.add(2);
        int nextPrime = 2;
        for(int idx=1;list.size()!=n;idx++){
            ++nextPrime;
            if(isPrime(nextPrime)){
                list.add(nextPrime);
            }
        }
        
        System.out.println(list.get(n-1));
    }
    
    private static boolean isPrime(int num){
        double limit = Math.sqrt(num);
        for(int i=2;i<=limit;i++){
            if(num%i==0 && i!=num)
                return false;
        }
        return true;
    }
}

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        int n = 1000;
        List<Integer> list = new ArrayList<>();
        list.add(2);
        int nextPrime = 2;
        for(int idx=1;list.size()!=n;idx++){
            ++nextPrime;
            if(isPrime(nextPrime)){
                list.add(nextPrime);
            }
        }
        
        System.out.println(list.get(n-1));
    }
    
    private static boolean isPrime(int num){
        double limit = Math.sqrt(num);
        for(int i=2;i<=limit;i++){
            if(num%i==0 && i!=num)
                return false;
        }
        return true;
    }
}
回复 原文
~没有更多了~

关于作者

云淡月浅

暂无简介

文章
评论
27 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

tomoekana

文章 0 评论 0

无边思念无边月

文章 0 评论 0

眼角的笑意。

文章 0 评论 0

在风中等你

文章 0 评论 0

是你

文章 0 评论 0

syong71

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文