1. Résoudre le nombre premier
1.1 Description
Tout d'abord, comprenons le concept, quel est ce qui est un nombre premiers? Numéro primaire: si un nombre ne peut être divisible que par 1 et lui-même, un tel nombre est appelé nombre premier, et le nombre correspondant est appelé numéro de somme. Sur la base de ce concept, nous pouvons rapidement penser à une méthode, qui doit commencer à partir de 1 et tester constamment pour voir s'il y a des nombres qui peuvent être divisés par eux de 1 à lui-même.
De ce point de vue, il est en fait très simple de trouver des nombres premiers. Y a-t-il un moyen plus pratique pour nous? Voici une méthode célèbre pour trouver des nombres premiers par Eratosthène.
1.2 Solution
Tout d'abord, vous pouvez utiliser des cercles pour résoudre ce problème. Divisez un nombre spécifié par tous les nombres plus petits que lui. Si vous pouvez le diviser, ce n'est pas un nombre premier. Cependant, comment réduire le nombre de chèques de cercles? Comment trouver tous les nombres premiers plus petits que n?
En supposant que le numéro à vérifier est n, en fait, vérifiez simplement le nombre racine de N. La raison est très simple. Supposons que A * B = N, si A est supérieur au nombre racine de N, en fait, vérifiez avant d'être inférieur à A peut d'abord vérifier que le nombre B peut être divisible. Cependant, l'utilisation du numéro racine du programme aura le problème de la précision, vous pouvez donc utiliser i * i <= n pour la vérification et l'exécution sera plus rapide.
Supposons qu'il y ait un tamis pour stocker 1 ~ n, par exemple:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ......... n
Tamisez d'abord les multiples de 2:
2 3 5 7 9 11 13 15 17 19 21 ......... n
Puis tamisez les multiples de 3:
2 3 5 7 11 13 17 19 ......... n
Ensuite, tamisez les multiples de 5, puis tamisez le nombre premier de 7, puis tamisez les multiples de 11 ..., de cette manière, les nombres laissés à la fin sont tous des nombres premiers, il s'agit de la méthode de dépistage des eratosthènes (EratoSthenesshenessiepemethod).
Le nombre de contrôles peut être réduit. En fait, vérifiez simplement 6n + 1 et 6n + 5, c'est-à-dire, sautez les multiples de 2 et 3 directement, de sorte que l'action IF Vérification dans le programme peut être réduite.
1.3 Code
import java.util. *; classe publique prime {public static int [] findPrimes (final int max) {int [] prime = new int [max + 1]; ArrayList list = new ArrayList (); pour (int i = 2; i <= max; i ++) prime [i] = 1; pour (int i = 2; i * i <= max; i ++) {// Cela peut être amélioré if (prime [i] == 1) {for (int j = 2 * i; j <= max; j ++) {if (j% i == 0) prime [j] = 0; }}} pour (int i = 2; i <max; i ++) {if (prime [i] == 1) {list.add (new Integer (i)); }} int [] p = new int [list.size ()]; Objet [] objs = list.toArray (); for (int i = 0; i <p.length; i ++) {p [i] = ((entier) objs [i]). intValue (); } return p; } public static void main (String [] args) {int [] prime = prime.findPrimes (1000); for (int i = 0; i <prime.length; i ++) {System.out.print (prime [i] + ""); } System.out.println (); }}2. Factorisation
2.1 Description
Comme indiqué ci-dessus, comprenons d'abord ce qu'est la factorisation? La conversion d'un nombre en produit de plusieurs autres nombres est appelée factorisation. Après avoir compris ce concept, nous devrions être en mesure de comprendre que nous résolvons un facteur d'un nombre de somme par rapport à la solution ci-dessus pour résoudre le nombre premier.
La factorisation utilise essentiellement la valeur plus petite que le nombre d'entrée en tant que diviseur et la supprime avec le numéro d'entrée. S'il peut être divisé, il sera considéré comme un facteur. La solution plus rapide consiste à trouver tous les nombres premiers plus petits que le nombre et à essayer de voir s'il peut être divisé.
2.2 Code
import java.util.arraylist; Facteur de classe publique {public static int [] facteur (int num) {int [] pnum = prime.findPrimes (num); ArrayList list = new ArrayList (); for (int i = 0; pnum [i] * pnum [i] <= num;) {if (num% pnum [i] == 0) {list.add (new Integer (pnum [i])); num / = pnum [i]; } else i ++; } list.add (new Integer (num)); int [] f = new int [list.size ()]; Objet [] objs = list.toArray (); pour (int i = 0; i <f.length; i ++) {f [i] = ((entier) objs [i]). intValue (); } return f; } public static void main (String [] args) {int [] f = factor.factor (100); for (int i = 0; i <f.length; i ++) {System.out.print (f [i] + ""); } System.out.println (); }}3. Résumé
La résolution de nombres premiers et de factorisation est la compétence de base des programmes et des algorithmes d'apprentissage, et vous devez les maîtriser avec compétence. Le code ici n'a qu'un petit nombre de commentaires, ce qui peut être un peu difficile pour les débutants, mais c'est la première étape pour entrer dans le palais des algorithmes de programme. Vous pouvez copier ce code sur votre machine et remplir les commentaires étape par étape pour rendre votre processus de programme plus clair.
Ce qui précède est tout le contenu de cet article sur la mise en œuvre de la programmation Java pour réaliser des nombres premiers et un code de factorisation, et j'espère que cela sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler!