1. Resuelve el número primo
1.1 Descripción
En primer lugar, comprendamos el concepto, ¿cuál es lo que son los números primos? Número primo: si un número solo puede ser divisible por 1 y en sí mismo, dicho número se llama número primo, y el número correspondiente se llama número de suma. Según este concepto, podemos pensar rápidamente en un método, que es comenzar desde 1 y probar constantemente para ver si hay números que pueden dividirse por ellos de 1 a sí mismo.
Desde este punto de vista, en realidad es muy simple encontrar números primos. ¿Hay una manera más conveniente para nosotros? Aquí hay un método famoso para encontrar números primos de Eratosthenes.
1.2 Solución
En primer lugar, puede usar círculos para resolver este problema. Divida un número especificado por todos los números más pequeños que él. Si puede dividirlo, no es un número primo. Sin embargo, ¿cómo reducir la cantidad de cheques de círculos? ¿Cómo encontrar todos los números primos más pequeños que n?
Suponiendo que el número a verificar es n, de hecho, solo verifique el número raíz de N. La razón es muy simple. Suponga que a*b = n, si A es mayor que el número raíz de N, de hecho, verifique antes de ser menos que A puede verificar primero que el número B pueda ser divisible. Sin embargo, el uso del número raíz en el programa tendrá el problema de la precisión, por lo que puede usar i*i <= n para verificar y la ejecución será más rápida.
Supongamos que hay un tamiz para almacenar 1 ~ n, por ejemplo:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ......... N
Primero tamice los múltiplos de 2:
2 3 5 7 9 11 13 15 15 17 19 21 ......... N
Luego tamice los múltiplos de 3:
2 3 5 7 11 13 17 19 ......... n
Luego, tamice los múltiplos de 5, luego tamice el número primo de 7, luego tamice los múltiplos de 11 ..., de esta manera, los números que quedan al final son todos números primos, este es el método de detección de Eratosthenes (Eratostesievemethod).
El número de cheques puede reducirse. De hecho, simplemente verifique 6n+1 y 6n+5, es decir, omita los múltiplos de 2 y 3 directamente, de modo que la acción de verificación if en el programa se pueda reducir.
1.3 Código
import java.util.*; public class Prime {public static int [] findPrimes (final int max) {int [] prime = new int [max+1]; ArrayList list = new ArrayList (); para (int i = 2; i <= max; i ++) prime [i] = 1; for (int i = 2; i*i <= max; i ++) {// Esto se puede mejorar si (prime [i] == 1) {for (int j = 2*i; j <= max; j ++) {if (j % i == 0) Prime [j] = 0; }}} para (int i = 2; i <max; i ++) {if (prime [i] == 1) {list.add (nuevo entero (i)); }} int [] p = new int [list.size ()]; Objeto [] objs = list.toarray (); para (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); for (int i = 0; i <prime.length; i ++) {system.out.print (prime [i]+""); } System.out.println (); }}2. Factorización
2.1 Descripción
Como se muestra arriba, ¡entendamos primero qué es la factorización? La conversión de un número en el producto de varios otros números se llama factorización. Después de comprender este concepto, deberíamos poder entender que estamos resolviendo un factor de un número de suma en comparación con la solución anterior para resolver el número primo.
La factorización básicamente usa el valor más pequeño que el número de entrada como divisor, y lo elimina con el número de entrada. Si se puede dividir, se considerará como un factor. La solución más rápida es encontrar todos los números primos más pequeños que el número e intentar ver si se puede dividir.
2.2 Código
import java.util.arrayList; Factor de clase pública {Public static int [] factor (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 (nuevo entero (pnum [i])); num /= pnum [i]; } else i ++; } list.add (nuevo entero (num)); int [] f = new int [list.size ()]; Objeto [] objs = list.toarray (); para (int i = 0; i <f.length; i ++) {f [i] = (((integer) 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. Resumen
Resolver números primos y factorización es la habilidad básica de los programas de aprendizaje y los algoritmos, y debe dominarlos de manera competente. El código aquí solo tiene un pequeño número de comentarios, lo que puede ser un poco difícil para principiantes, pero este es el primer paso para ingresar al palacio de los algoritmos del programa. Puede copiar este código a su máquina y completar los comentarios paso a paso para que el proceso de su programa sea más claro.
Lo anterior es todo el contenido de este artículo sobre la implementación de la programación de Java para lograr números primos y código de factorización, y espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo.