Javaでの再帰を使用した素数の検索

Question

私は学校でこの問題を書いていますが、いくつか問題があります。実際に素数を計算することはできません。明らかに、番号4のメインからテストを実行すると、4が素数であることがわかります。どのように式を書く必要がありますか？

手順は次のとおりです。 （別の再帰関数のラッパーをまたはこの関数を作る）この関数を記述するために

使用再帰

* a number is prime if it is divisible only by itself and 1 
* (that is, if it is not divisible by any number between * itself and 1; 
* we can optimize and just check between 2 and the square root of the number). 
* by convention, 1 is NOT prime 
* this function returns true if its parameter is prime, false otherwise. 
* One way to do this is to test all numbers between 2 and n; if any of them  
* divides it, then it is not prime. If you reach the end, then it is. 
* Examples: 
* isPrime(1) => false 
* isPrime(2) => true 
* isPrime(3) => true 
* isPrime(4) => false 
*/ 



public static boolean isPrime(int n) 
{ 
    if (n == 0 || n == 1) { 
     return false; 
    } if (n == 2 || n == 3) { 
     return true; 
    } if (Math.sqrt(n) % 2 == 0) { 
     return true; 
    }else 
     return isPrime(n); 
    } 

以下のコードは、私の教授は、学年にプログラムを使用していますgrader.javaからです。 isprimeメソッドの呼び出しがいくつかあります。それは常に4（私は理由を参照してください... 4平方キロ％2 == 0）と4はプライム＃ではないハングアップするようです。素数で

  public void testIsPrime() 
{ 
    Assert.assertEquals("1 is not prime", false,Assignment4.isPrime(1)); 
    Assert.assertEquals("2 is prime", true,Assignment4.isPrime(3)); 
    Assert.assertEquals("4 is not prime", false,Assignment4.isPrime(4)); 
    Assert.assertEquals("7 is prime", true,Assignment4.isPrime(7)); 
    Assert.assertEquals("9 is not prime", false,Assignment4.isPrime(9)); 
    Assert.assertEquals("35 is not prime", false,Assignment4.isPrime(35)); 
    Assert.assertEquals("37 is prime", true,Assignment4.isPrime(37));   
} 

Answer 1

割り当てがあなたの重要なヒント与えている：

またはこの機能に別の再帰的なオーバーラップを作るに機能

public static boolean isPrime_helper(int number, int divisor) 
{ 
    /* write code to return true if divisor is > square root of number */ 
    /* which can also be expressed divisor squared is > number */ 

    /* write code here to test if divisor divides number without remainder */ 
    /* and return false if it does. Otherwise: */ 

    return isPrime_helper(number, divisor + 2); 
} 

public static boolean isPrime(int number) 
{ 
    /* deal with the special cases 2, < 2, and even numbers here */ 
    /* Otherwise: */ 

    return isPrime_helper(number, 3); 
} 

Answer 2

、あなたは2でそれを分割することができますし、number%2が0であるか、数はあなたが返す必要が2であれば、したがって、2で割ることができないはずなので2が素数することはできません偽です。

数値が2でないか、0で割り切れない場合は、関数内でforループを使用して他の数値を調べることができます。

次のコードを見てみましょう、それは何が起こっているか理解するのに役立ちます：

public boolean isPrime (int number){ 
    if ((number%2)==0 && number != 2) { 
     return false; 
    } 
    else { 
     for (int i =3; i*i<number; i++) 
     { 
      if (number%i ==0) 
       return false; 
     } 
     return true; 
    } 

Answer 3

cdlaneの答えには基本的な修正があります。私はちょうどあなたの試行が動作しないことを知っていることを確認したい。 2つの致命的な問題があります。

1. 再帰の単純化はありません。基底ケース（0-3）に当たっていない場合は、と同じ番を返し、無限ループにあなたを投げ込みます。
2. sqrt句は不必要で間違っています。数字のsqrtが偶数の場合、はを素数にすることはできません。これは再帰を止めるためのテストであるはずですか？