英文:
Project Euler problem 10, wrong answer but why (Java)
问题
public static void main(String args[]) {
int[] primes = new int[2000000];
int index=0;
int ans=0;
//finding primes and populating array
for (int candidate=2; candidate<=2000000; candidate++) {
System.out.println(candidate); //so I can watch the numbers go up
for (int divisor=1; divisor<=candidate; divisor++) {
if (candidate%divisor==0 && candidate==divisor) {
primes[index]=candidate;
index++;
break;
}
if (candidate%divisor==0 && candidate!=divisor && divisor!=1) {
break;
}
}
}
//adding primes
for (int m=0; m<primes.length; m++) {
ans+=primes[m];
}
System.out.println(ans);
}
英文:
newbie question I know, but I can't figure out what the error is in my code for this question. The problem asks to get the sum of all prime numbers below 2,000,000.
I can't figure out why my code works for smaller sets, yet when I wait patiently for my code to finish for 2,000,000 it spits out a wrong answer. 1,179,908,154 in this case.
DISCLAIMER I realize the code I've written is extraordinarily inefficient/wasteful and that I should use the Sieve of Eratosthenes among other things. I'm just trying to figure out why it gives the wrong answer.
public static void main(String args[]) {
int[] primes = new int[2000000];
int index=0;
int ans=0;
//finding primes and populating array
for (int candidate=2; candidate<=2000000; candidate++) {
System.out.println(candidate); //so I can watch the numbers go up
for (int divisor=1; divisor<=candidate; divisor++) {
if (candidate%divisor==0 && candidate==divisor) {
primes[index]=candidate;
index++;
break;
}
if (candidate%divisor==0 && candidate!=divisor && divisor!=1) {
break;
}
}
}
//adding primes
for (int m=0; m<primes.length; m++) {
ans+=primes[m];
}
System.out.println(ans);
}
答案1
得分: 1
我认为你的问题出在ans
的类型上。
在Java中,int类型占据4个字节,这意味着它们只能存储范围在-2,147,483,648到2,147,483,647之间的数字。
所有小于两百万的质数的总和远远超过了这些值。
这里发生的情况是你的int
变量溢出并且“绕回去”(它从最大值跳到最小值)。
尝试将ans
的类型更改为long。
英文:
I think your problem lies within the type of ans
.
In Java, ints are 4 bytes long, which means they can only store numbers ranging from -2,147,483,648 to 2,147,483,647.
The sum of all prime numbers below two million is far greater than these values.
What's happening here is that your int
variable overflows and "goes around" (it "skips" from the maximum value to the minimum value).
Try changing the type of ans
to long.
答案2
得分: 0
我将相同错误的结果从我的Java程序加载到本地的Scala REPL中。
scala> org.oeis.primes.PrimeLister.listPrimes(2_000_000)
res3: java.util.ArrayList[Integer] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...
scala> import collection.JavaConverters._
import collection.JavaConverters._
scala> res3.asScala
warning: object JavaConverters in package collection is deprecated (since 2.13.0):
Use `scala.jdk.CollectionConverters` instead
res4: scala.collection.mutable.Buffer[Integer] = Buffer(2, 3, 5, 7, 11, 13, 17, 19, ...
scala> res4.toList
res5: List[Integer] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
scala> res5.scanLeft(0)(_ + _)
res7: List[Int] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...
scala> res5.scanLeft(0L)(_ + _)
res12: List[Long] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...
scala> res7.takeRight(1)
res15: List[Int] = List(1179908154)
scala> res12.takeRight(1)
res16: List[Long] = List(142913828922)
因此,是的,请尝试使用 long
类型来累加这些质数。
英文:
I get the same wrong result with my Java program loaded into my local Scala REPL.
scala> org.oeis.primes.PrimeLister.listPrimes(2_000_000)
res3: java.util.ArrayList[Integer] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...
scala> import collection.JavaConverters._
import collection.JavaConverters._
scala> res3.asScala
^
warning: object JavaConverters in package collection is deprecated (since 2.13.0):
Use `scala.jdk.CollectionConverters` instead
res4: scala.collection.mutable.Buffer[Integer] = Buffer(2, 3, 5, 7, 11, 13, 17, 19, ...
scala> res4.toList
res5: List[Integer] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
scala> res5.scanLeft(0)(_ + _)
res7: List[Int] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...
scala> res5.scanLeft(0L)(_ + _)
res12: List[Long] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...
scala> res7.takeRight(1)
res15: List[Int] = List(1179908154)
scala> res12.takeRight(1)
res16: List[Long] = List(142913828922)
So yeah, try using long
to add up the primes.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论