Java에서 최소 공배수를 계산하는 방법-Java베이스-php.cn

Java에서 최소 공배수를 계산하는 방법

문제 설명:

양의 정수 N이 주어지면 1~N 중에서 무작위로 선택한 3개의 숫자를 묻습니다. 그 최소값은 무엇인가요? 여러 개일 수 있습니다.

입력 형식:

양의 정수 N을 입력하세요.

출력 형식:

찾은 최소 공배수를 나타내는 정수를 출력합니다.

샘플 입력:

샘플 출력:

504

데이터 규모 및 규칙:

1 <= N <= 106

추천 온라인 학습 비디오 튜토리얼:javacourse

# #아이디어:

먼저 몇 가지 개념을 선언합니다.

0이 아닌 인접한 두 자연수의 최소공배수는 인접한 두 홀수의 최소값입니다. 배수는 두 개의 인접한 짝수(0 제외)의 최소 공배수는 곱의 절반입니다.

이제 세 숫자의 최소 공배수까지 N의 패리티에 따라 두 가지 상황이 있습니다.

1. n이 홀수인 경우: n, n -1, n-2의 곱

2. n이 짝수인 경우: n-1, n-2, n-3은 답이 더 큰 경우의 집합입니다. 현재 값보다 클 경우에만 이 값보다 커야 합니다. 세 숫자의 곱인 경우 숫자 중 하나만 n으로 변경될 수 있으며 세 숫자도 상대적으로 소수여야 합니다. n, n-2, n-3 짝수와 홀수는 분명히 서로 소수가 아닙니다. n, n-1, n-3은 짝수이고 홀수입니다. n, n-1, n-2 짝수와 홀수는 분명히 서로 소수가 아닙니다.

그렇다면 답은 n-1, n-2, n-3 또는 n, n-1, n-3밖에 될 수 없습니다. 그러나 n과 n-3은 홀수이자 짝수이기는 하지만 연속적이지 않으며 세 숫자 5, 6, 3과 같이 상대적으로 소수가 아닐 수도 있습니다.

n은 홀수입니다: n, n-1, n-2

n은 짝수입니다. n은 3의 배수입니다. n-1, n-2 , n-3# #

n은 3n의 배수가 아닙니다. n, n-1, n-3

예는 다음과 같습니다.

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input=new Scanner(System.in); long N=input.nextLong(); long temp=0; if(N<=2){ System.out.println(N); } else if(N%2==0){ temp=(N-1)*(N-2)*(N-3); if(N%3!=0){ temp=Math.max(temp,N*(N-1)*(N-3)); } System.out.println(temp); } else { System.out.println(N*(N-1)*(N-2)); } } }

로그인 후 복사

# # 팁: N<3의 경우를 고려하고, 이 질문에서는 long을 사용하는 것에 주의하세요.