Comment trouver les nombres premiers Java

Qu'est-ce qu'un nombre premier?

Quand j'essaie de résoudre le problème des professionnels compétitifs, je ne me souviens pas de ce que j'ai appris quand j'étais étudiant.

Qu'est-ce qu'un nombre premier, selon Wikipedia

Un nombre premier est un entier naturel supérieur à 1 et qui n'a qu'une fraction positive et lui-même. Il peut être reformulé comme un nombre naturel dans lequel le nombre de fractions positives est de 2.

C'est vrai. En d'autres termes, c'est un entier supérieur à ** 1, un nombre qui ne peut être divisé que par 1 et vous-même **.

Programme de jugement des nombres premiers

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "N'est pas un nombre premier.");
      return;
    }

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "N'est pas un nombre premier.");
        return;
      }
    }
    
    System.out.println(target + "Est un nombre premier.");
  }
}

Commentaire

Un entier supérieur à 1

    if (target < 2) {
      System.out.println(target + "N'est pas un nombre premier.");
      return;
    }

Ici, nous vérifions si l'entier est supérieur à ** 1, ce qui est significatif car c'est un nombre premier **. S'il est inférieur à 2, vous savez que ce n'est pas un nombre premier, alors sortez-le et terminez le processus immédiatement.

Un nombre qui ne peut être divisé que par 1 et vous-même

Après tout, c'est cette partie qui devient le cœur.

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "N'est pas un nombre premier.");
        return;
      }
    }
    
    System.out.println(target + "Est un nombre premier.");

Dans l'instruction for, divisez par le nombre de 2 à cible-1 un par un et vérifiez s'il est divisible. S'il y a même un nombre divisible, ce nombre n'est pas un nombre premier, alors sortez-le et terminez le processus avec return.

S'il n'y a pas de nombre divisible, «cible» est un nombre premier. : applaudir:

Accélérant

Comme moyen simple de savoir s'il s'agit d'un nombre premier, j'ai utilisé la méthode ci-dessus de division par 1 et tous les nombres à l'exception du nombre cible. Cependant, avec cette méthode, plus le nombre d'objets à examiner est grand, plus le calcul prendra du temps.

Donc, comme vous l'avez dit dans les commentaires, il semble que vous puissiez juger s'il s'agit d'un nombre premier ou non en ne vérifiant que les valeurs sous la racine carrée.

Pourquoi jusqu'à la racine carrée

Un nombre premier était un nombre qui n'était divisible que par 1 et lui-même, mais les autres nombres sont appelés nombres composés. En d'autres termes, un nombre composé est un nombre qui n'est ni 1 ni un nombre premier. En d'autres termes, le nombre composé est ** 1 et a au moins une fraction autre que lui-même **.

De plus, le nombre de composites a la propriété de ** avoir une fraction de ** √n ou moins.

Le nombre de composites a une fraction de √n ou moins

Pourquoi peut-on dire que le nombre composé a une fraction inférieure à √n?

Premièrement, le nombre composé n peut être exprimé par «n = ab» car il existe des nombres naturels a et b qui ne sont pas 1. Si n n'a pas de fraction inférieure ou égale à √n, alors √n <a, √n <b. √n est supérieur à 0, donc si √n <a, √n <b (n n'a pas de fraction inférieure ou égale à √n), √n√n (= n) ʻest ʻab Il sera plus petit que «n = ab». Par conséquent, on peut dire que n a un diviseur de √n ou moins.

En d'autres termes, si n est un nombre composé, il a une fraction inférieure à √x, donc si vous vérifiez s'il y a une fraction inférieure à √x, Vous pouvez déterminer si le nombre est un nombre premier!

Programme de jugement de Kai / nombre premier

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "N'est pas un nombre premier.");
      return;
    }
    if (target % 2 == 0) { //Le nombre pair revient en premier
      System.out.println(target + "N'est pas un nombre premier.");
      return;
    }

    for (int i = 3; i <= Math.sqrt(target); i+=2) {
      if (target % i == 0) {
        System.out.println(target + "N'est pas un nombre premier.");
        return;
      }
    }

    System.out.println(target + "Est un nombre premier.");
  }
}