1. 소수를 해결하십시오
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 17 18 19 20 21 ......... N
먼저 2의 배수를 체로 섭취하십시오.
2 3 5 7 9 11 13 15 17 19 21 ......... n
그런 다음 3의 배수를 체로 체로 체계하십시오.
2 3 5 7 11 13 17 19 ......... n
그런 다음 5의 배수를 체질한 다음 소수 7을 체질한 다음 11의 배수를 체질하십시오. 이런 식으로, 끝에 남은 숫자는 모두 소수이며, 이것은 eratosthenes 스크리닝 방법 (eratosthenesseievemethod)입니다.
수표 수를 줄일 수 있습니다. 실제로, 6n+1 및 6n+5를 확인하십시오. 즉, 2와 3의 배수를 직접 건너 뛰면 프로그램의 IF 확인 작업을 줄일 수 있습니다.
1.3 코드
java.util.*; Public Class Prime {public static int [] findprimes (Final int max) {int [] prime = new int [max+1]; ArrayList List = New ArrayList (); for (int i = 2; i <= max; i ++) 프라임 [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; }}} for (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] = ((정수) objs [i]). intvalue (); } 반환 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 [] 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 (new Integer (pnum [i])); num /= pnum [i]; } else i ++; } list.add (새 정수 (num)); int [] f = new int [list.size ()]; Object [] objs = list.toArray (); for (int i = 0; i <f.length; i ++) {f [i] = ((정수) objs [i]). intvalue (); } 반환 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 프로그래밍 구현에 관한이 기사의 모든 내용이며, 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨주십시오.