7

我正在做 Project Euler 的第 7 题。我应该做的是计算第 10,001个素数。（素数是一个大于 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）运行会导致堆栈溢出。为什么，我该如何解决这个问题？

4

13 回答 13

30

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

于 2010-03-21T02:30:03.880 回答
8

使用“埃拉托色尼筛”

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);
    }
}
于 2010-03-22T14:42:54.507 回答
4

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

于 2010-03-21T02:30:36.260 回答
2

我最近解决了这个问题。我建议用Eratosthenes 筛生成你的素数，比如所有素数 < 100 万。这不是一个很难实现的算法，而且对于您需要的素数数量来说它相当快。

于 2010-03-21T02:34:13.657 回答
2

某些语言的编译器（例如许多函数式和半函数式语言，如 Lisp）会像您使用的那样将尾递归转换为迭代，但（显然）Java 编译器并没有为您这样做。结果，每个递归调用都在使用堆栈空间，最终你用完并且堆栈溢出。

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

于 2010-03-21T02:35:14.820 回答
1

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

如果你改变你的策略来测试每个较小的素数的可分性，你会节省大量的计算。

于 2010-03-21T06:38:21.593 回答
1 
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);
    }
}
于 2011-06-29T03:53:25.503 回答
0

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

由于函数 Prime 是递归的，它可以调用自身的次数总是有系统限制。

但是，您的系统上可能有足够的内存达到 10001。Java 允许您设置 VM 使用的最大内存量（堆栈、堆等）。增加堆栈内存号，您可能会成功。看到这个页面

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

对于一些 Java VM 选项。

于 2010-03-21T02:30:13.803 回答
0

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

于 2010-03-22T14:50:17.130 回答
0 
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++;
        }
    }
}

这是我的工作答案。

于 2012-05-16T10:15:12.677 回答
0

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

对低于被测试数的平方根的所有数测试可分性就足够了。就 OP 代码而言，这意味着不是从 开始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)的可分性，测试并向上计数。whileX = 3N % XX += 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 个素数，而是它上面的数字。

于 2012-05-17T09:55:40.927 回答
0

在 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");
}
于 2013-01-21T03:04:33.867 回答
0

公共课编{

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

}

于 2013-09-04T02:31:03.633 回答