Test de nombres premiers très simple - Je ne comprends pas la boucle for

Je suis pratiquant passé les examens de base de java examen, et je trouve qu'il est difficile de faire une boucle for de travail pour tester si un nombre est premier. Je ne veux pas compliquer par l'ajout de mesures d'efficacité pour un plus grand nombre, juste quelque chose qui serait au moins de travail pour les 2 chiffres.

Au moment où il retourne toujours false, même si n EST un nombre premier.

Je pense que mon problème est que j'obtiens quelque chose de mal avec la boucle de lui-même et où mettre le "return true;" et "return false;"... je suis sûr que c'est une erreur fondamentale que je suis en train de faire...

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

La raison pour laquelle je ne pouvais pas trouver de l'aide ailleurs sur stackoverflow est parce que des questions similaires ont été pour demander une plus compliqué la mise en œuvre de disposer d'un moyen plus efficace de le faire.

source d'informationauteur BexLE

31

Votre for boucle a un petit problème. Il doit être: -
```
for (i = 2; i < n; i++)  //replace `i <= n` with `i < n`
```
Bien sûr, vous ne voulez pas de vérifier le reste quand n est divisé par n. Il vous donnera toujours 0.

En fait, vous pouvez même réduire le nombre d'itérations par l'évolution de la condition de: - i <= n /2. Depuis n ne peut pas être divisé par un nombre supérieur à n /2sauf lorsque nous considérons nque nous n'avons pas à envisager.

Vous pouvez changer votre for boucle pour: -
```
for (i = 2; i <= n / 2; i++)  
```

Vous pouvez arrêter beaucoup plus tôt et passer à travers la boucle rapide avec:

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;
}

3

Erreur est i<=n
```
for (i = 2; i<n; i++){
```
3

Vous devriez écrire i < nparce que la dernière étape de l'itération va vous donner true.

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;
  }
}

Avec ce code nombre divisible par 3 sera ignoré pour la boucle de code d'initialisation.

Pour la boucle d'itération sera également ignorer les multiples de 3.

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

Vous pouvez également utiliser quelques calculs simples de la propriété dans votre boucle for.

Un nombre " n " sera un nombre premier si et seulement si elle est divisible par lui-même ou 1.
Si un nombre n'est pas un nombre premier il sera équipé de deux facteurs:
```
n = a * b
```
vous pouvez utiliser la boucle for pour vérifier jusqu'à la racine carrée du nombre " n " au lieu d'aller tout le chemin à 'n'. Comme si 'a' et 'b' sont supérieures à la racine carrée du nombre "n", a*b doit être supérieure à "n". Si au moins l'un des facteurs doit être inférieur ou égal à la racine carrée.

de sorte que votre boucle, pourrait être quelque chose comme ci-dessous:
```
for(int i=2; i<=Math.sqrt(n); i++)
```
En faisant cela vous permettrait de réduire considérablement le temps d'exécution de la complexité du code.
Je pense qu'il serait réduit à O(n/2).

L'un de la façon la plus rapide est en boucle que jusqu'à la racine carrée de 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
    }

0

Vous êtes à la vérification de i<=n.Alors, quand i==nvous obtiendrez 0 seulement et il retournera false toujours.Essayez i<=(n/2).Pas besoin de vérifier jusqu'à i<n.

La mentionnés ci-dessus algorithme traite 1 en tant que premier bien qu'il ne l'est pas.
Donc voici la solution.

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;
}

Bien, pour la boucle a un problème. Voici le 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;
}

Faire la Java 8 est plus agréable et plus propre

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

Vous devez vous connecter pour publier un commentaire.