返回语句中堆栈溢出错误(Stack overflow error in return statement)

当我提交到画布时得到堆栈溢出错误，但它在Visual Studio代码中运行正常，任何人都知道问题是什么？

这是错误：

Exception in thread "main" java.lang.StackOverflowError at Phi.gcd(Phi.java:14

这是作业：

欧拉的总体函数（也称为φ（n））测量与n相比素数小于n的正整数的数量。如果它们的gcd为1，则两个数字是相对的。例如：φ（9）= 6，因为1,2,4,5,7和8相对于9是质数。有关Euler的总体函数的更多信息可以在此找到Wiki页面。
n Relatively Prime φ(n) 2 1 1 3 1,2 2 4 1,3 2 5 1,2,3,4 4 6 1,5 2 7 1,2,3,4,5,6 6 8 1,3,5,7 4 9 1,2,4,5,7,8 6 10 1,3,7,9 4
编写一个函数int phi(int n) ，它将整数n作为输入并返回φ（n），并提供一个提示用户输入整数i的main() ，调用函数φ（i）并打印结果。输入i上限为250000。

计算φ（n）的闭式公式为：其中p1，p2，...，pm是除数n的素数。

你的程序的输出应该看起来像下面的例子一样运行。
Enter a positive integer n: 8 Phi(n): 4

这是我的代码：

import java.util.Scanner; public class Phi { static int gcd(int a, int b) { if (a == 0 || b == 0) return 0; if (a == b) return a; if (a > b) return gcd(a-b, b); return gcd(a, b-a); } static int phi(int n) { int count=0; for(int i = 1; i < n; ++i) { if(gcd(n, i) == 1) { count++; } } return count; } public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Enter a positive integer n: ");; int n = in.nextInt(); System.out.printf("Phi(%d): %d\n", n, phi(n)); } }

Getting a stack overflow error when i submit to canvas but it runs fine in Visual Studio Code, anyone know what the issue is?

Here is the error:

Exception in thread "main" java.lang.StackOverflowError at Phi.gcd(Phi.java:14

Here is the assignment:

Euler's totient function, otherwise known as φ(n), measures the number of positive integers relatively prime to n that are less than n. Two numbers are relatively prime if their gcd is 1. For example: φ(9) = 6 because 1, 2, 4, 5, 7, and 8 are relatively prime to 9. More information about Euler's totient function can be found at this Wiki page.
n Relatively Prime φ(n) 2 1 1 3 1,2 2 4 1,3 2 5 1,2,3,4 4 6 1,5 2 7 1,2,3,4,5,6 6 8 1,3,5,7 4 9 1,2,4,5,7,8 6 10 1,3,7,9 4
Write a function int phi(int n) that takes an integer n as an input and returns φ(n), and a main() that prompts a user for an integer i, calls the function φ(i), and prints the result. The upper limit for the input i is 250000.

The closed form formula for computing φ(n) is: where p1, p2, ..., pm are prime numbers that divide the number n.

The output of your program should look and function like the examples shown below.
Enter a positive integer n: 8 Phi(n): 4

And here is my code:

import java.util.Scanner; public class Phi { static int gcd(int a, int b) { if (a == 0 || b == 0) return 0; if (a == b) return a; if (a > b) return gcd(a-b, b); return gcd(a, b-a); } static int phi(int n) { int count=0; for(int i = 1; i < n; ++i) { if(gcd(n, i) == 1) { count++; } } return count; } public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Enter a positive integer n: ");; int n = in.nextInt(); System.out.printf("Phi(%d): %d\n", n, phi(n)); } }

最满意答案

这是因为您的递归GCD方法非常缓慢地收敛到GCD的值。例如，如果您传递250000和1，则您的方法将使用250000个堆栈帧，这比大多数JVM为您分配的数量要多。

一种解决方法是用迭代重写欧几里得的GCD算法。另一个解决方案是使用更快的算法：

int gcd(int a, int b) { return (b != 0) ? gcd(b, a % b) : a; }

This is because your recursive GCD method converges to the value of GCD very slowly. For example, if you pass 250000 and 1, your method would use 250000 stack frames, more than most JVMs would allocate for you.

One solution is to rewrite Euclid's GCD algorithm with iterations. Another solution is to use a faster algorithm:

int gcd(int a, int b) { return (b != 0) ? gcd(b, a % b) : a; }

更多推荐