Я столкнулся с некоторыми проблемами с рекурсией в Java

Question

Задача состоит в том, чтобы реализовать программу, которая подсчитывает, сколько существует различных сумм простых чисел для данного числа sumtoBreak.

Метод primeSum должен вычесть все возможные простые числа currprime из числа sumtoBreak, пока sumtoBreak не станет равным нулю, а затем вернуть (в сумме) единицу для каждой возможности. Чтобы учесть все возможности, на каждом этапе рецессии он вызывает себя

1. с sumtoBreak - currprime плюс
2. вызывает себя с nextPrime.

Моя проблема в том, что java не вернет ничего, если sumtoBreak не будет нулем в самом начале.
Буду рад любому совету!

Вот код (я знаю, что скобка в коде с вложенными операторами if избыточны, но я просто хотел убедиться, что это не проблема):

Вот фиксированный код:

public class PrimeSum {
    public static boolean isPrime(int primecandidate) {
        int count = 0;
        for (int i = 2; i <= primecandidate / 2; i++) {
            if (primecandidate % i == 0)
                count++;
        }
        if (count == 0)
            return true;
        else
            return false;
    }

    public static int nextPrime(int currprime) {
        int j = currprime + 1;
        while (!isPrime(j))
            j++;
        return j;
    }

    public static int primeSum(int sumtoBreak, int currprime) {
        if (sumtoBreak == 0) {
            return 1;
        } else {
            if (sumtoBreak < 0 || currprime > sumtoBreak) {
                return 0;
            } else {
                return primeSum(sumtoBreak, nextPrime(currprime)) + primeSum(sumtoBreak - currprime, currprime);
            }
        }

    }

    public static void main(String[] args) {
        System.out.println(primeSum(Integer.parseInt(args[0]), 2));
    }
}

Answer 1

Это не отвечает на ваш вопрос, но исправляет ошибку в вашем методе isPrime и вычисляет результат намного быстрее:

private static boolean isPrime(final int primecandidate) {

    if ( primecandidate <  2) {        // 0 & 1 are NOT Prime
        return false;
    }
    if ((primecandidate & 0x1) == 0) { // Even is NOT Prime...
        return primecandidate  == 2;   // ...except for 2 (and 0).
    }
    for (int i = 2, iMax = (int) Math.sqrt(primecandidate); i <= iMax; i++) {
        if (primecandidate % i == 0) {
            return false;
        }
    }
    return true;
}

Обратите внимание на следующее :

• конечный аргумент primecandidate помечен как конечный
• , он исправляет результат для 0 & 1 в false
• метод помечен как приватный
• iMax - это Sqrt (primecandidate), а не primecandidate / 2
• iMax вычисляется один раз, вместо каждой итерации
• Я использую стратегию, которую я называю «если все готово, будь готов».
  Значение: не устанавливайте флаг (в вашем случае), просто уходите!

Обратите внимание, что есть функция apache commons Math3 ...

org. apache .commons.math3.primes.Primes.isPrime (j)

Это значительно медленнее для значений smalli sh ( <= Short.MAX_VALUE) <br>Это несколько быстрее для больших значений sh (около Integer.MAX_VALUE)

Существует также BigIntege Функция r.isProbablePrime (...), но мой бенчмарк показывает, что она довольно медленная.

Надеюсь, это немного поможет?

Answer 2

Некоторые вещи, которые вы, возможно, пропустили:

в функции, оператор return завершает (break) функцию немедленно. Так что в

if(...) { return ...; }
else {...}

→ else избыточно, как будто условие истинно, функция уже завершена (break)

Что-то вроде a==0 имеет boolean значение (true или false). Так что

if (count == 0) {return false; }

else {return true;}

можно сократить до return count!=0;

Я рекомендую всегда использовать фигурные скобки, поскольку что-то вроде if(i==0) ++i; break; означает if(i==0) {++i;}. break; будет вызван в любом случае.

public static boolean
isPrime(int n)
{
  if(n==0 || n==1) { return false; }

  for(int i= 2; i <= n/2; ++i)
  {
    if(n%i == 0) { return false; } //we know, n is not a prime,
                                   //so function can break here
  }
  return true; //since for all values of i, the function did not break,
               //n is a prime
}

Я буду sh у вас много мотивации для кодирования на будущее!