“Project Euler问题10,答案错误但是为什么(Java)”

huangapple go评论65阅读模式
英文:

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&lt;=2000000; candidate++) {
			System.out.println(candidate); //so I can watch the numbers go up
			for (int divisor=1; divisor&lt;=candidate; divisor++) {
				
				if (candidate%divisor==0 &amp;&amp; candidate==divisor) {
					primes[index]=candidate;
					index++;
					break;
				}
				
				if (candidate%divisor==0 &amp;&amp; candidate!=divisor &amp;&amp; divisor!=1) {
					break;
				}				
				
			}
		}
		
		//adding primes
		for (int m=0; m&lt;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&gt; 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&gt; import collection.JavaConverters._
import collection.JavaConverters._
scala&gt; 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&gt; res4.toList
res5: List[Integer] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
scala&gt; res5.scanLeft(0)(_ + _)
res7: List[Int] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...
scala&gt; res5.scanLeft(0L)(_ + _)
res12: List[Long] = List(0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, ...
scala&gt; res7.takeRight(1)
res15: List[Int] = List(1179908154)
scala&gt; res12.takeRight(1)
res16: List[Long] = List(142913828922)

So yeah, try using long to add up the primes.

huangapple
  • 本文由 发表于 2020年9月23日 10:47:35
  • 转载请务必保留本文链接:https://go.coder-hub.com/64020313.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定