1. Lösen Sie die Primzahl
1.1 Beschreibung
Lassen Sie uns zunächst das Konzept verstehen. Was sind Primzahlen? Primzahl: Wenn eine Zahl nur durch 1 und sich selbst teilbar sein kann, wird eine solche Zahl als Primzahl bezeichnet, und die entsprechende Zahl wird als Summennummer bezeichnet. Basierend auf diesem Konzept können wir uns schnell an eine Methode vorstellen, die von 1 beginnen und ständig testen soll, ob es Zahlen gibt, die von ihnen von 1 in sich selbst geteilt werden können.
Aus dieser Sicht ist es tatsächlich sehr einfach, Primzahlen zu finden. Gibt es eine bequemere Möglichkeit für uns? Hier ist eine berühmte Methode, um Primzahlen von Eratosthenes zu finden.
1.2 Lösung
Zunächst können Sie Kreise verwenden, um dieses Problem zu lösen. Teilen Sie eine bestimmte Zahl durch alle Zahlen, die kleiner sind als sie. Wenn Sie es teilen können, ist es keine Primzahl. Wie können Sie jedoch die Anzahl der Kreiseprüfungen reduzieren? Wie finde ich alle Primzahlen kleiner als n?
Unter der Annahme, dass die zu überprüfende Nummer n ist, überprüfen Sie in der Tat die Wurzelnummer von N. Der Grund ist sehr einfach. Nehmen wir an, dass a*b = n, wenn a größer als die Wurzelnummer von N ist, prüfen Sie tatsächlich, bevor Sie weniger als ein können, ob die Zahl B zuerst teilbar sein kann. Die Verwendung der Stammnummer im Programm hat jedoch das Problem der Genauigkeit, sodass Sie i*i <= n für die Überprüfung verwenden können und die Ausführung schneller wird.
Nehmen wir an, dass es ein Sieb gibt, das 1 ~ n speichert, zum Beispiel:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ......... n
Erster die Vielfachen von 2 sieben:
2 3 5 7 9 11 13 15 17 19 21 ......... n
Dann sieben Sie die Vielfachen von 3:
2 3 5 7 11 13 17 19 ......... n
Dann über die Vielfachen von 5 sieben, dann die Primzahl von 7 sieben, dann die Vielfachen von 11 ... Auf diese Weise sind die am Ende verbleibenden Zahlen alle Primzahlen, dies ist die Eratosthenes -Screening -Methode (Eratosthingievemethod).
Die Anzahl der Schecks kann reduziert werden. Überprüfen Sie einfach 6N+1 und 6N+5, dh die Vielfachen von 2 und 3 direkt überspringen, damit die IF -Überprüfungsaktion im Programm reduziert werden kann.
1.3 Code
import Java.util.*; public class prime {public static int [] findprimes (endgültig int max) {int [] prime = new int [max+1]; ArrayList List = new ArrayList (); für (int i = 2; i <= max; i ++) Prime [i] = 1; für (int i = 2; i*i <= max; i ++) {// Dies kann verbessert werden, wenn (Prime [i] == 1) {für (int j = 2*i; j <= max; j ++) {if (j % i == 0) Prime [j] = 0; }}} für (int i = 2; i <max; i ++) {if (prime [i] == 1) {list.add (New Integer (i)); }} int [] p = new int [list.size ()]; Object [] objs = list.toArray (); für (int i = 0; i <p.Length; i ++) {p [i] = ((integer) objs [i]). intValue (); } return p; } public static void main (String [] args) {int [] prime = prime.findprimes (1000); für (int i = 0; i <prime.length; i ++) {System.out.print (prime [i]+""); } System.out.println (); }}2. Faktorisierung
2.1 Beschreibung
Wie oben gezeigt, verstehen wir zunächst, was Faktorisierung ist? Die Umwandlung einer Zahl in das Produkt mehrerer anderer Zahlen wird als Faktorisierung bezeichnet. Nach dem Verständnis dieses Konzepts sollten wir in der Lage sein zu verstehen, dass wir im Vergleich zur obigen Lösung einen Faktor einer Summenzahl lösen, um die Primzahl zu lösen.
Die Faktorisierung verwendet im Grunde den Wert, den der Wert kleiner als die Eingangszahl als Divisor, und entfernt ihn mit der Eingangsnummer. Wenn es geteilt werden kann, wird es als Faktor angesehen. Die schnellere Lösung besteht darin, alle Primzahlen kleiner als die Zahl zu finden und zu versuchen, zu sehen, ob sie geteilt werden kann.
2.2 Code
Import Java.util.ArrayList; öffentlicher Klassenfaktor {public static int [] faktor (int num) {int [] pnum = prime.findprimes (num); ArrayList List = new ArrayList (); für (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 ()]; Object [] objs = list.toArray (); für (int i = 0; i <f.Length; i ++) {f [i] = ((Ganzzahl) objs [i]). intValue (); } return f; } public static void main (String [] args) {int [] f = faktor.factor (100); für (int i = 0; i <f.Length; i ++) {System.out.print (f [i]+""); } System.out.println (); }}3. Zusammenfassung
Das Lösen von Primzahlen und Faktorisierung ist die grundlegende Fähigkeit von Lernprogrammen und Algorithmen, und Sie sollten sie kompetent beherrschen. Der Code hat hier nur eine kleine Anzahl von Kommentaren, die für Anfänger etwas schwierig sein können. Dies ist jedoch der erste Schritt, um in den Palast der Programmalgorithmen einzutreten. Sie können diesen Code in Ihren Computer kopieren und Schritt für Schritt die Kommentare ausfüllen, um Ihr Programm zu löschen.
Das obige ist der gesamte Inhalt dieses Artikels über die Implementierung von Java -Programmierungen, um Primzahlen und Faktorisierungscode zu erreichen, und ich hoffe, dass es für alle hilfreich sein wird. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen!