wake-up-neo.com

Sehr einfacher Primzahlentest - Ich glaube, ich verstehe die for-Schleife nicht

Ich übe frühere Prüfungsarbeiten für eine Java-Grundprüfung, und es fällt mir schwer, eine for-Loop-Arbeit durchzuführen, um zu testen, ob eine Zahl eine Primzahl ist. Ich möchte es nicht komplizierter machen, indem es Effizienzmessungen für größere Zahlen hinzufügt, etwas, das zumindest für zweistellige Zahlen funktionieren würde.

Im Moment gibt es immer false zurück, auch wenn n IS eine Primzahl ist.

Ich denke, mein Problem ist, dass ich mit der for-Schleife selbst etwas falsch mache und wo das "return true" steht. und "return false;" ... Ich bin sicher, dass es ein wirklich grundlegender Fehler ist, den ich mache ...

public boolean isPrime(int n) {
    int i;
    for (i = 2; i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Der Grund, warum ich an anderer Stelle keine Hilfe für stackoverflow finden konnte, liegt darin, dass ähnliche Fragen nach einer komplizierteren Implementierung verlangten, um effizienter zu arbeiten.

13
BexLE

Ihre for-Schleife hat ein kleines Problem. Es sollte sein: -

for (i = 2; i < n; i++)  // replace `i <= n` with `i < n`

Natürlich möchten Sie den Rest nicht überprüfen, wenn n durch n geteilt wird. Es wird Ihnen immer 1 geben.

Sie können sogar die Anzahl der Iterationen reduzieren, indem Sie die Bedingung wie folgt ändern: i <= n / 2. Da n nicht durch eine Zahl größer als n / 2 geteilt werden kann, es sei denn, wir betrachten n, die wir überhaupt nicht berücksichtigen müssen.

Sie können also Ihre for-Schleife folgendermaßen ändern: -

for (i = 2; i <= n / 2; i++)  
31
Rohit Jain

Sie können viel früher anhalten und die Schleife schneller überspringen mit:

public boolean isPrime(long n) {
    // fast even test.
    if(n > 2 && (n & 1) == 0)
       return false;
    // only odd factors need to be tested up to n^0.5
    for(int i = 3; i * i <= n; i += 2)
        if (n % i == 0) 
            return false;
    return true;
}
31
Peter Lawrey

Sie sollten i < n schreiben, da Sie beim letzten Iterationsschritt true erhalten.

3
Zoltán Tamási

Fehler ist i <= n

for (i = 2; i<n; i++){
3
public class PrimeNumberCheck {
  private static int maxNumberToCheck = 100;

  public PrimeNumberCheck() {
  }

    public static void main(String[] args) {
      PrimeNumberCheck primeNumberCheck = new PrimeNumberCheck();

      for(int ii=0;ii < maxNumberToCheck; ii++) {
        boolean isPrimeNumber = primeNumberCheck.isPrime(ii);

      System.out.println(ii + " is " + (isPrimeNumber == true ? "prime." : "not prime."));
    }
  }

  private boolean isPrime(int numberToCheck) {    
    boolean isPrime = true;

    if(numberToCheck < 2) {
      isPrime = false;
    }

    for(int ii=2;ii<numberToCheck;ii++) {
      if(numberToCheck%ii == 0) {
        isPrime = false;
        break;
      }
    }

    return isPrime;
  }
}
2
user2033388

Bei dieser durch 3 teilbaren Codenummer wird die Initialisierung des Schleifencodes übersprungen. 
Bei Schleifeniteration werden auch Vielfache von 3 übersprungen.

private static boolean isPrime(int n) {

    if ((n > 2 && (n & 1) == 0) // check is it even
       || n <= 1  //check for -ve
       || (n > 3 && (n % 3 ==  0))) {  //check for 3 divisiable
            return false;
    }

    int maxLookup = (int) Math.sqrt(n);
    for (int i = 3; (i+2) <= maxLookup; i = i + 6) {
        if (n % (i+2) == 0 || n % (i+4) == 0) {
            return false;
        }
    }
    return true;
}
1

Eine der schnellsten Methoden führt nur bis zur Quadratwurzel von n.

  private static boolean isPrime(int n){
        int square = (int)Math.ceil((Math.sqrt(n)));//find the square root
        HashSet<Integer> nos = new HashSet<>(); 
        for(int i=1;i<=square;i++){
            if(n%i==0){
                if(n/i==i){
                    nos.add(i);
                }else{
                    nos.add(i);
                    int rem = n/i;
                    nos.add(rem);
                }
            }
        }
        return nos.size()==2;//if contains 1 and n then prime
    }
1
Ram Kumar

Sie können auch eine einfache Math-Eigenschaft in Ihrer for-Schleife verwenden. 

Eine Zahl 'n' ist genau dann eine Primzahl, wenn sie durch sich selbst oder 1. .__ teilbar ist. Wenn eine Zahl keine Primzahl ist, hat dies zwei Faktoren: 

n = a * b

sie können die for-Schleife verwenden, um bis zur Zahl 'n' zu prüfen, anstatt bis 'n' zu gehen. Wenn 'a' und 'b' beide größer sind als das Quadrat der Zahl 'n', wäre a * b größer als 'n'. Daher muss mindestens einer der Faktoren kleiner oder gleich der Quadratwurzel sein. 

ihre Schleife wäre also wie folgt: 

for(int i=2; i<=Math.sqrt(n); i++)

Dadurch würden Sie die Laufzeitkomplexität des Codes drastisch reduzieren. Ich denke, es würde sich auf O (n/2) auswirken. 

1
Nitesh Joshi

Der Java 8-Weg ist schöner und sauberer

    private static boolean isPrimeA(final int number) {
        return IntStream
               .rangeClosed(2, number/2)
               .noneMatch(i -> number%i == 0);
    }
0
Sal

Sie überprüfen i<=n. Wenn i==n, erhalten Sie nur 0 und es wird immer false zurückgegeben. Versuchen Sie i<=(n/2). Keine Notwendigkeit, bis i<n zu überprüfen.

0
Renjith

Nun, die for-Schleife hat ein Problem. Hier ist der Code,

public static boolean checkPrimeNUmber(int number) 
{ 
   if(number <= 1) 
   { 
      return false; 
   } 
   for(int a = 2; a < Math.sqrt(number); a++) 
   { 
      if(number % a == 0) 
      { 
         return false; 
      } 
   } 
   return true;
}
0
Shiva

Der oben erwähnte Algorithmus behandelt 1 als Primzahl, obwohl dies nicht der Fall ist. .__ Hier ist also die Lösung.

static boolean isPrime(int n) {
  int perfect_modulo = 0;
  boolean prime = false;

  for ( int i = 1; i <=  n; i++ ) {
    if ( n % i == 0 ) {
      perfect_modulo += 1;
    }
  }
  if ( perfect_modulo == 2 ) {
    prime = true;
  }

  return prime;
}
0
kxhitiz