1. Решите основное число
1.1 Описание
Прежде всего, давайте поймем концепцию, что такое основные цифры? Основное число: если число можно делить только на 1 и само по себе, такое число называется основным числом, а соответствующее число называется номером суммы. Основываясь на этой концепции, мы можем быстро подумать о методе, который должен начинаться с 1 и постоянно проверять, чтобы увидеть, есть ли цифры, которые можно разделить на них от 1 до себя.
С этой точки зрения, на самом деле очень просто найти основные числа. Есть ли более удобный способ для нас? Вот известный метод поиска основных цифр от Eratosthenes.
1.2 Решение
Прежде всего, вы можете использовать круги для решения этой проблемы. Разделите указанное число на все числа меньше его. Если вы можете обсудить это, это не главное число. Однако как уменьшить количество проверок кругов? Как найти все основные числа меньше n?
Предполагая, что номер, который необходимо проверить, составляет n, на самом деле, просто проверьте номер корня N. Причина очень проста. Предположим, что a*b = n, если A больше корневого числа n, фактически проверьте, прежде чем быть меньше, чем A может сначала проверить, что число B можно делить. Однако использование корневого числа в программе будет иметь проблему точности, поэтому вы можете использовать i*i <= n для проверки, и выполнение будет быстрее.
Давайте предположим, что есть сито для хранения 1 ~ N, например:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 16 17 18 19 20 21 ......... n n
Сначала просеивайте мультипликации 2:
2 3 5 7 7 9 11 13 15 17 19 21 ......... n
Затем просеивайте мультипликации 3:
2 3 5 7 7 11 13 17 19 ......... n
Затем просеяйте кратные 5, затем просеяйте первичное количество 7, затем просеяйте кратные из 11 ..., таким образом, числа, оставленные в конце, являются основными числами, это метод скрининга Eratosthenes (eratostesseievemethod).
Количество чеков может быть уменьшено. На самом деле, просто проверьте 6n+1 и 6n+5, то есть пропустите несколько магистралей 2 и 3 напрямую, чтобы было уменьшено проверка действия в программе.
1.3 код
Импорт java.util.*; public class prime {public static int [] findprimes (final int max) {int [] prime = new int [max+1]; ArrayList List = new ArrayList (); для (int i = 2; i <= max; i ++) prime [i] = 1; for (int i = 2; i*i <= max; i ++) {// Это можно улучшить, если (prime [i] == 1) {for (int j = 2*i; j <= max; j ++) {if (j % i == 0) prime [j] = 0; }}} для (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 (); for (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. Факторизация
2.1 Описание
Как показано выше, давайте сначала поймем, что такое факторизация? Преобразование числа в продукт нескольких других чисел называется факторизацией. Понимая эту концепцию, мы должны быть в состоянии понять, что мы решаем коэффициент числа сумм по сравнению с вышеуказанным решением для решения основного числа.
Факторизация в основном использует значение, меньшее, чем входное число в качестве делителя, и удаляет его с входным номером. Если это можно разделить, это будет рассматриваться как фактор. Более быстрое решение состоит в том, чтобы найти все основные числа меньше, чем число, и попытаться увидеть, можно ли его разделить.
2.2 код
импортировать java.util.arraylist; Фактор публичного класса {public static int [] фактор (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 (новое целое число (pnum [i])); num /= pnum [i]; } else i ++; } list.add (new Integer (num)); int [] f = new int [list.size ()]; Object [] objs = list.toarray (); for (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. Резюме
Решение основных чисел и факторизации является основным навыком учебных программ и алгоритмов, и вы должны овладеть ими опытно. Код здесь имеет лишь небольшое количество комментариев, которые могут быть немного трудными для начинающих, но это первый шаг к входу во дворец алгоритмов программы. Вы можете скопировать этот код на свою машину и заполнить комментарии шаг за шагом, чтобы прояснить процесс программы.
Выше приведено все содержание этой статьи об реализации программирования Java для достижения основных чисел и кода факторизации, и я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это!