Project Euler # 10 Java-решение не работает

Question

Я пытаюсь найти сумму простых чисел

Печать 'sum' дает: 1308111344, что неверно.

Edit: Спасибо за помощь. Изменил int на long и <на <=, и он работал безупречно, за исключением того, что был неэффективным способом поиска простых чисел:) </p>

/*
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
*/
class Helper{
 public void run(){
  Integer sum = 0;
  for(int i = 2; i < 2000000; i++){
   if(isPrime(i))
    sum += i;   
  }
  System.out.println(sum);
 }

 private boolean isPrime(int nr){
  if(nr == 2)
   return true;
  else if(nr == 1)
   return false;
  if(nr % 2 == 0)
   return false;

  for(int i = 3; i < Math.sqrt(nr); i += 2){
   if(nr % i == 0)
    return false;
  }  
  return true;  
 }
}   
class Problem{
 public static void main(String[] args){
  Helper p = new Helper();
p.run();
}
}

Answer 1

Результат будет слишком большим, чтобы поместиться в целое число, поэтому вы получаете переполнение .Попробуйте использовать BigInteger или long .В этом случае достаточно длинного.

Answer 2

Вы рассматриваете как простые числа, которые делятся только на их квадратный корень (например, 25). Вместо i < Math.sqrt(nr) попробуйте i <= Math.sqrt(nr).

Кстати, это действительно неэффективный способ найти простые числа.

Answer 3

Ваш isPrime не работает для квадратов.isPrime (9) возвращает true.

Answer 4

, используя Сито Эратосфена эффективно, я решил проблему, вот мой код

public class SumOfPrime {

    static void findSum()
    {
        long i=3;
        long sum=0;
        int count=0;
        boolean[] array = new boolean[2000000];
        for(long j=0;j<array.length;j++)
        {
         if((j&1)==0)
          array[(int)j]=false;   
         else    
         array[(int)j]=true;
        }
        array[1]=false;
        array[2]=true;
        for(;i<2000000;i+=2)
        { 
            if(array[(int)i] & isPrime(i))
            {   
                array[(int)i]=true;
                //Sieve of Eratosthenes
                for(long j=i+i;j<array.length;j+=i)
                    array[(int)j]=false;
            }
        }
        for(int j=0;j<array.length;j++)
        {
            if(array[j])
            {   
             //System.out.println(j);
             count++;   
             sum+=j;
            }
        }   
        System.out.println("Sum="+sum +" Count="+count);
    }
    public static boolean isPrime(long num)
    {
        boolean flag=false;
        long i=3;
        long limit=(long)Math.sqrt(num);
        for(;i<limit && !(flag);i+=2)
        {
            if(num%i==0)
            {
                flag=false;
                break;
            }   
        }
        if(i>=limit)
         flag=true;
        return flag;
    }

    public static void main(String args[])
    {
        long start=System.currentTimeMillis();
        findSum();
        long end=System.currentTimeMillis();
        System.out.println("Time for execution="+(end-start)+"ms");
    }

}

и вывод

Sum=142913828922 Count=148933
Time for execution=2360ms

если у вас есть сомнения, пожалуйста, скажите

Answer 5

Как уже говорилось, ошибок было две:

• вы использовали int, который недостаточно велик, чтобы вместить эту сумму .. вы должны были использовать long
• вы использовали < вместо этого <=, и это был неправильный предохранитель для цикла

Кроме того, что вы делаете, это действительно неэффективно, не вдаваясь слишком глубоко в этот класс алгоритмов (как Миллер-Рабин тест) Я бы посоветовал вам взглянуть на Сито Эратосфена .. действительно старый подход, который учит, как решать сложные проблемы простым способомулучшите элегантность и эффективность с помощью компромисса памяти.

Это действительно умно: он отслеживает значение boolean для каждого простого числа до ваших 2 миллионов, которое утверждает, является ли это число простым или нет.Затем, начиная с первого простого числа, он исключает все последовательные числа, полученные путем умножения простого числа, которое он анализирует, на другое число.Конечно, больше идет и меньше цифр, которые он должен будет проверить (так как он уже исключил их)

Код довольно прост (просто написал его на лету, не проверил):

    boolean[] numbers = new boolean[2000000];
    long sum = 0;

    for (int i = 0; i < numbers.length; ++i)
        numbers[i] = true;

    for (int i = 2; i < numbers.length; ++i)
        if (!numbers[i])
            continue;
        else {
            int j = i + i;
            while (j < 2000000) {                   
                numbers[j] = false;
                j += i;
            }           
        }

    for (int i = 2; i < 2000000; ++i)
        sum += numbers[i] ? i : 0;

    System.out.println(sum);

Конечно, этот подход все еще не подходит для больших чисел (потому что он все равно должен найти все предыдущие простые числа и из-за памяти), но это хороший пример для начинающих задуматься о проблемах ..

Answer 6

Вот мое решение

  public class ProjectEuler {

    public static boolean isPrime(int i) {
        if (i < 2) {
            return false;
        } else if (i % 2 == 0 && i != 2) {
            return false;
        } else {
            for (int j = 3; j <= Math.sqrt(i); j = j + 2) {
                if (i % j == 0) {
                    return false;
                }
            }

            return true;
        }
    }


    public static long sumOfAllPrime(int number){
        long sum = 2;

        for (int i = 3; i <= number; i += 2) {
            if (isPrime(i)) {
                sum += i;
            }
        }

        return sum;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(sumOfAllPrime(2000000));
    }
}