이 페이지는 코딩도장 데이터의 읽기 전용 정적 보관본입니다.

여러 가지 수의 최대공약수, 최소공배수 찾기

3개 이상의 여러 가지의 수가 주어졌을 때, 공약수, 최대공약수, 최소공배수를 찾는 알고리즘을 구하시오.

6015240, 1507968, 4530816

의 공약수, 최대공약수, 최소공배수를 구하시오.

2019/05/22 11:23

lovegalois2

24개의 풀이가 있습니다.

import functools


def gcd(a: int, b: int):
    a, b = max(a, b), min(a, b)
    while b:
        a, b = b, a % b
    return a


def lcm(a: int, b: int):
    return a * b // gcd(a, b)


def cds(num: int):
    return [x for x in range(1, num + 1) if num % x == 0]


input_list = [6015240, 1507968, 4530816]
result_gcd = functools.reduce(gcd, input_list)
result_lcm = functools.reduce(lcm, input_list)

print(f"GCD: {result_gcd}")
print(f"LCM: {result_lcm}")
print(f"Divisors: {cds(result_gcd)}")

2019/05/22 12:27

mohenjo

n=list(map(int,input("3개 이상의 여러 가지 숫자를 입력하십시오: ").split(",")))
d={} #최대공약수를 구하기 위해 딕셔너리 사용
for num in n:
    s=set() #입력한 각 숫자의 공약수를 구하기 위함
    for k in range(1,int(num**(1/2))+1):
        if num%k==0:
            d[k]=d.get(k,0)+1
            d[num//k]=d.get(num//k,0)+1
            s.add(k)
            s.add(num//k)
        else:
            continue
    print(s) #입력한 각 숫자의 공약수 집합 출력
elst=[]
for key in list(d.keys()):
    if d[key]==len(n): #입력한 숫자들의 갯수와 똑같은 value값을 가지는 key들이 입력한 숫자들의 공약수임.
        elst.append(key)
print(elst) #입력한 숫자들의 공약수 리스트 출력 
a=max(elst)
for num in n:
    a*=int(num/max(elst))
print(max(elst)) #최대공약수  (#72: 6015240, 1507968, 4530816입력 시)    
print(a) #최소공배수  (#7927869963847680: 6015240, 1507968, 4530816입력 시)

2020/01/14 00:20

박시원

최소공배수는 6434959386240 입니다. - ­박철희, 2021/09/21 22:52
def gcd(x, y):
    if y: return gcd(y, x%y)
    else: return x

def lcm(x, y):
    return int(x * y / gcd(x, y))

def run():
    from functools import reduce

    lis = [6015240, 1507968, 4530816]
    rst = [reduce(gcd, lis), reduce(lcm, lis)]
    rst.append([x for x in range(1, rst[0]+1) if rst[0]%x == 0])
    print(rst)

2019/06/05 14:04

이진형

def gcd(a,b):
    if b>a:
        return gcd(b,a)
    elif b==0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    return a*b//gcd(a,b)

def faclist(n):
    fac=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            fac.append(i)
            fac.append(n//i)
    faclist=list(set(fac))
    faclist.sort()
    return faclist


while True:
    user=input("Input space-separated integers: ")
    numlist=[int(x) for x in user.split()]
    GCD=numlist[0]
    LCM=numlist[0]
    for i in range(1,len(numlist)):
        GCD=gcd(GCD,numlist[i])
        LCM=lcm(LCM,numlist[i])
    cofaclist=','.join([str(x) for x in faclist(GCD)])
    print("Common factors: {}".format(cofaclist))
    print("Greatest common divisor = {}".format(GCD))
    print("Lowest common multiple = {}".format(LCM))
    print()


2019/05/23 10:31

ykleeac

list = [6015240, 1507968, 4530816]

def aliquot (num) : ## 주어진 수의 약수로 이루어진 집합 생성
  list = set([])
  for i in range(1,num+1):
    if int(num) % i == 0:
      list.add(i)
  return list

def CD(list): ## 공약수
  list1 = aliquot(list[0])
  for i in range(1,len(list)):
    list1 = list1 & aliquot(list[i])
  return list1

def GCD(list): ## 최대공약수
  return max(CD(list))

def LCM(list): ## 최소공배수
  data = GCD(list)
  for i in list:
    data = data * int(i/GCD(list))
  return data

print("최소 공배수 :",LCM(list))
print("최대 공약수 :",GCD(list))
print("공약수 :",CD(list))

by python3.7

2019/05/24 23:02

_styl2s

package ssy.hr.ga.car.biz;

import java.util.ArrayList;
import java.util.Scanner;

class test 
{
    public static void main(String[] args) {

     Scanner scan = new Scanner(System.in);

     System.out.println("값을 입력하세요");

     int a = scan.nextInt();
     int b = scan.nextInt();
     int c = 0 ;
     ArrayList<Integer>  array = new ArrayList<Integer>();

     for(int i = 1 ; i<= a; i++){
         if(a%i==0 && b%i ==0){
            array.add(i);
         }

         if(b%a==0){
             c = b;
         }else{
             c = a*b;
         }

     }

System.out.println("공약수 : "+ array);
System.out.println("최대공약수 : "+ array.get(array.size()-1));
System.out.println("최소공배수 : " + c);
}
}

2019/06/04 13:21

김종만

N개의 최소공배수

class NLCM{
    public long nlcm(int[] num) {
        long answer = num[0];
        long small = 0;
        long big = 0;

        for (int i = 1; i < num.length; i++) {
            small = Math.min(answer, num[i]);
            big = Math.max(answer, num[i]);

            answer = (small * big) / gcd(small, big);
        }
        return answer;
    }

    public static long gcd(long small, long big) {
        long answer = 0;

        for (int i = 1; i <= small; i++) {
            if (small % i == 0 && big % i == 0) answer = i;
        }

        return answer;
    }
    public static void main(String[] args) {
        NLCM c = new NLCM();
        int[] ex = { 6015240, 1507968, 4530816 };
        System.out.println(c.nlcm(ex));
    }
}

2019/06/13 18:33

KingCoding

def gcd(n, m):
    return n if m is 0 else gcd(m, n % m)


def lcm(n, m):
    return n * m // gcd(n, m)


def factors(n):
    return sorted(m for m in range(1, n+1) if n % m == 0)


a, b, c = 6015240, 1507968, 4530816
G = gcd(gcd(a, b), c)
print(factors(G), G, lcm(lcm(a, b), c))

2019/07/05 16:53

Noname

6015240의 약수 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 22, 24, 28, 30, 31, 33, 35, 36, 40, 42, 44, 45, 49, 55, 56, 60, 62, 63, 66, 70, 72, 77, 84, 88, 90, 93, 98, 99, 105, 110, 120, 124, 126, 132, 140, 147, 154, 155, 165, 168, 180, 186, 196, 198, 210, 217, 220, 231, 245, 248, 252, 264, 279, 280, 294, 308, 310, 315, 330, 341, 360, 372, 385, 392, 396, 420, 434, 440, 441, 462, 465, 490, 495, 504, 539, 558, 588, 616, 620, 630, 651, 660, 682, 693, 735, 744, 770, 792, 840, 868, 882, 924, 930, 980, 990, 1023, 1078, 1085, 1116, 1155, 1176, 1240, 1260, 1302, 1320, 1364, 1386, 1395, 1470, 1519, 1540, 1617, 1705, 1736, 1764, 1848, 1860, 1953, 1960, 1980, 2046, 2156, 2170, 2205, 2232, 2310, 2387, 2520, 2604, 2695, 2728, 2772, 2790, 2940, 3038, 3069, 3080, 3234, 3255, 3410, 3465, 3528, 3720, 3906, 3960, 4092, 4312, 4340, 4410, 4557, 4620, 4774, 4851, 5115, 5208, 5390, 5544, 5580, 5880, 6076, 6138, 6468, 6510, 6820, 6930, 7161, 7595, 7812, 8085, 8184, 8680, 8820, 9114, 9240, 9548, 9702, 9765, 10230, 10780, 11160, 11935, 12152, 12276, 12936, 13020, 13640, 13671, 13860, 14322, 15190, 15345, 15624, 16170, 16709, 17640, 18228, 19096, 19404, 19530, 20460, 21483, 21560, 22785, 23870, 24255, 24552, 26040, 27342, 27720, 28644, 30380, 30690, 32340, 33418, 35805, 36456, 38808, 39060, 40920, 42966, 45570, 47740, 48510, 50127, 54684, 57288, 60760, 61380, 64680, 66836, 68355, 71610, 78120, 83545, 85932, 91140, 95480, 97020, 100254, 107415, 109368, 122760, 133672, 136710, 143220, 150381, 167090, 171864, 182280, 194040, 200508, 214830, 250635, 273420, 286440, 300762, 334180, 401016, 429660, 501270, 546840, 601524, 668360, 751905, 859320, 1002540, 1203048, 1503810, 2005080, 3007620, 6015240]

1507968의 약수 [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 17, 18, 21, 22, 24, 28, 32, 33, 34, 36, 42, 44, 48, 51, 56, 63, 64, 66, 68, 72, 77, 84, 88, 96, 99, 102, 112, 119, 126, 128, 132, 136, 144, 153, 154, 168, 176, 187, 192, 198, 204, 224, 231, 238, 252, 264, 272, 288, 306, 308, 336, 352, 357, 374, 384, 396, 408, 448, 462, 476, 504, 528, 544, 561, 576, 612, 616, 672, 693, 704, 714, 748, 792, 816, 896, 924, 952, 1008, 1056, 1071, 1088, 1122, 1152, 1224, 1232, 1309, 1344, 1386, 1408, 1428, 1496, 1584, 1632, 1683, 1848, 1904, 2016, 2112, 2142, 2176, 2244, 2448, 2464, 2618, 2688, 2772, 2856, 2992, 3168, 3264, 3366, 3696, 3808, 3927, 4032, 4224, 4284, 4488, 4896, 4928, 5236, 5544, 5712, 5984, 6336, 6528, 6732, 7392, 7616, 7854, 8064, 8568, 8976, 9792, 9856, 10472, 11088, 11424, 11781, 11968, 12672, 13464, 14784, 15232, 15708, 17136, 17952, 19584, 20944, 22176, 22848, 23562, 23936, 26928, 29568, 31416, 34272, 35904, 41888, 44352, 45696, 47124, 53856, 62832, 68544, 71808, 83776, 88704, 94248, 107712, 125664, 137088, 167552, 188496, 215424, 251328, 376992, 502656, 753984, 1507968]

4530816의 약수 [1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 27, 32, 36, 38, 46, 48, 54, 57, 64, 69, 72, 76, 81, 92, 96, 108, 114, 128, 138, 144, 152, 162, 171, 184, 192, 207, 216, 228, 276, 288, 304, 324, 342, 368, 384, 414, 432, 437, 456, 513, 552, 576, 608, 621, 648, 684, 736, 828, 864, 874, 912, 1026, 1104, 1152, 1216, 1242, 1296, 1311, 1368, 1472, 1539, 1656, 1728, 1748, 1824, 1863, 2052, 2208, 2432, 2484, 2592, 2622, 2736, 2944, 3078, 3312, 3456, 3496, 3648, 3726, 3933, 4104, 4416, 4968, 5184, 5244, 5472, 6156, 6624, 6992, 7296, 7452, 7866, 8208, 8832, 9936, 10368, 10488, 10944, 11799, 12312, 13248, 13984, 14904, 15732, 16416, 19872, 20976, 21888, 23598, 24624, 26496, 27968, 29808, 31464, 32832, 35397, 39744, 41952, 47196, 49248, 55936, 59616, 62928, 65664, 70794, 79488, 83904, 94392, 98496, 119232, 125856, 141588, 167808, 188784, 196992, 238464, 251712, 283176, 377568, 503424, 566352, 755136, 1132704, 1510272, 2265408, 4530816]

최대 공약수: 72

최소 공배수: 7927869963847680.0

def factor(number):             #약수 구하기
    fac=[]
    for i in range(1,number+1):
        if number%i==0:
            fac.append(i)
    return fac##

def factors(numbers):           #약수를 딕셔너리로
    facs=dict()
    for i in range(len(numbers)):
        facs[numbers[i]]=factor(numbers[i])
    return facs

def gcf(n,m):                   #두수의 공약수 구하기
    if n<m:
        n,m=m,n
    if m==0:
        return n
    return gcf(n%m,m)

def gcfs(numbers):              #셋이상 수의 공약수
    i=0
    while True:
        try:
            fact=gcf(gcf(numbers[i],numbers[i+1]),numbers[i+2])
        except IndexError:
            break
        i+=1
    return fact

def lcm(numbers):               #최소공배수
    M=1
    cnt=len(numbers)
    D=pow(gcfs(numbers),cnt-1)

    for i in numbers:
        M*=i
    return M/D

numbers=list(map(int,input('숫자 입력(2개이상):').split(" ")))


facs=factors(numbers)
for i in range(len(facs)):
    print('{0}의 약수 {1}'.format(numbers[i],facs[numbers[i]]))

print('최대 공약수: {}'.format(gcfs(numbers)))

print('최소 공배수: {}'.format(lcm(numbers)))

2019/07/10 17:52

정환용

using System;
using System.Collections;

namespace studyyy
{
    class Program
    {
        static ArrayList Divisor_Array = new ArrayList();

        static int GCD_Method(int x, int y)
        {
            if(y == 0)
            {
                return x; 
            }

            else
            {
                return GCD_Method(y, x % y);
            }
        }


        static int LCM_Method(int x, int y)
        {
            return (x * y) / GCD_Method(x, y);
        }


        static void Divisor_Method(int x)
        {
            int k = 0;
            Divisor_Array.Clear();

            for (int i = 1; i <= x; i++)
            {
                if (x % i == 0)
                {
                    Divisor_Array.Add(i);
                }
            }

            Console.Write("공약수 : ");

            foreach (int Cw in Divisor_Array)
            {
                Console.Write(Cw + " ");
            }

            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            Console.Write("First Number : ");
            int x = Convert.ToInt32(Console.ReadLine());

            Console.Write("Second Number : ");
            int y = Convert.ToInt32(Console.ReadLine());

            Console.Write("Third Number : ");
            int z = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine();

            int GCD = GCD_Method(x, y);
            GCD = GCD_Method(GCD, z);

            int LCM = LCM_Method(x, y);
            LCM = LCM_Method(LCM, z);

            Divisor_Method(GCD);

            Console.WriteLine("최대공약수 : {0}", GCD);
            Console.WriteLine("최소공배수 : {0}", LCM);
        }
    }
}

초보 개발자 입니다. 피드백은 언제나 환영합니다.

2019/09/02 17:25

김저승

최소공배수는 값이 너무커서 못구했습니다..

public class 여러가지수의최대공약수_최소공배수찾기 {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        String[] str = scan.nextLine().split(", ");
        int[] nums = Arrays.stream(str).mapToInt(Integer::parseInt).toArray();
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        int a = 0;
        for(int i=0; i<nums.length; i++) {
            for(int j=1; j<nums[i]; j++) {
                if(nums[i]%j==0) {
                    list2.add(j);
                    a++;
                }
            }
        }

        for(int i=0; i<a; i++) {
            int count = 1;
            for(int j=i+1; j<list2.size(); j++) {
                if(list2.get(i)==list2.get(j)) {
                    count++;
                }
            }
            if(count==3) {
                list.add(list2.get(i));
            }
        }
        System.out.println("공약수 : " + list);
        System.out.println("최대공약수 : " + list.get(list.size()-1));

    }
}

2019/12/22 18:43

big Ko

n1 = int(input("n1 = ")) n2 = int(input("n2 = "))

gcd = n1

if n2 < n1 :

 gcd = n2

while True :

 if n1 % gcd == 0 and n2 % gcd == 0:
       break
 gcd -= 1

print("gcd = ", gcd)

칸이 적어서 ㅠㅠㅠ 2자연수의 최대 공약수만 간단하게 파이썬으로 구현해 보았습니다!

2020/01/14 21:47

최준혁

#파이썬

a=str(input('숫자를 입력해 주세요...')).split(',')
for i in range(len(a)):
    a[i]=int(a[i])
a.sort()

choidae=1

i=2
while (i<=a[0]+1):
    b=1 #값이 모두 나누어 떨어지면 1을 유지. 나누어 떨어지지않으면 0
    j=0
    while (j<len(a)):   #숫자들이 i로 나누어 떨어지는지 체크
        if a[j]%i!=0:
            b=0
        j+=1

    if b==1:                    #모든수가 i로 나누어 떨어지면 
        for j in range(len(a)):
            a[j]/=i             #모든수를 i로 나누고
        choidae*=i              #최대공약수를 i만큼 곱해준다
    else:
       i+=1

choiso=choidae
for i in range (len(a)):            #최소공배수는 최대공약수에 배열 a에 있는수를 모두 곱한 수
    choiso*=a[i]
print ('\n최대공약수=',choidae)
print ('최소공배수=',int(choiso))

gongyaksu=[]
for i in range (1,choidae+1):
    if choidae%i==0:
        gongyaksu.append(i)

print ('공약수=',gongyaksu)

2020/04/23 12:03

Buckshot

<결과> 숫자를 입력해 주세요...100,200,300,400 최대공약수= 100 최소공배수= 2400 공약수= [1, 2, 4, 5, 10, 20, 25, 50, 100] 숫자를 입력해 주세요...6015240, 1507968, 4530816 최대공약수= 72 최소공배수= 7927869963847680 공약수= [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72] - Buckshot, 2020/04/23 12:05
from functools import reduce
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return (x * y)/gcd(x, y)

if __name__ == '__main__':
    nums = 2, 6, 8, 14                                        #공약수: [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]
    gl_list = [reduce(f, nums) for f in [gcd, lcm]]           #최대공약수: 72
    cd = [d for d in range(1, gl_list[0]+1) if gl_list[0]%d == 0] #최소공배수: 6434959386240.0
    print('최대공약수: {}\n최소공배수: {}\n공약수: {}'.format(gl_list[0], gl_list[1], cd))

2020/05/19 12:37

Hwaseong Nam

위의 풀이중 최소공배수를 7927869963847680로 구한게 맞나요? 전 6434959386240 나온던데.....희안하네.. - Hwaseong Nam, 2020/05/19 12:40
6434959386240 이 맞습니다. 7927869963847680 은 옳은 답이 아닙니다. - ­박철희, 2021/09/21 22:49
#공약수
import math
def CD(a):
    yaksu = []
    for i in range(1,int(math.sqrt(a))):
            if a%i == 0:
                yaksu.append(i)
                yaksu.append(a//i)
    return yaksu

#공약수, 최대공약수 출력
def GCDofThreeNumbers(a, b, c):
    while b != 0:
        a, b = b, a%b
    while a != 0:
        c, a = a, c%a 
    return print(c,CD(c))

#최소공배수
def LMD(a,b,c):
    multiab = a*b
    while b != 0:
        a, b = b, a%b
    LMDab = multiab//a
    multiabc = LMDab*c
    while c != 0:
        LMDab, c = c, LMDab%c
    LMDabc = multiabc//LMDab
    return LMDabc

2020/07/05 10:12

Money_Coding

{.cpp}

include

include

using namespace std;

int gcd(int a, int b) { if (b == 0) { return a; } else return gcd(b, a % b); } int lcm(int a, int b) { int c = gcd(a, b); return a * b / c; }

int solution(vector arr) { int answer; for(int i = 1; i < arr.size(); i++){ if(i==1){ answer = lcm(arr[i-1], arr[i]); } else answer = lcm(answer, arr[i]); } return answer; }

2021/09/05 20:22

cho

잘못된 풀이들이 좀 보입니다. 최대공약수는 72이고 최소공배수는 6434959386240입니다. 6, 9, 12를 입력하면 3, 36이 나와야 합니다. 공약수는 각 수의 약수를 구하고 각 약수들을 set & set & set으로 묶으면 구할 수 있어서 생략했습니다.

def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

nums = list(map(int, input().split(', ')))
GCD = nums[0]
LCM = nums[0]
for i in range(1, len(nums)):
    # i번째 수까지의 최대공약수는 'i-1번째 수까지의 최대공약수'와 'i번째 수'의 최대공약수
    GCD = gcd(GCD, nums[i])
    # i번째 수까지의 최소공배수는 'i-1번째 수까지의 최소공배수'와 'i번째 수'의 최소공배수
    tmpGCD = gcd(LCM, nums[i])
    LCM = LCM * nums[i] // tmpGCD
print(GCD, LCM)

2021/09/21 22:32

­박철희

#codingdojing_gcd_of_multipleN
from functools import reduce

def gcd(a, b):

    if a%b == 0: return b
    else: return gcd(b, a%b)

def lcm(a, b):

    return a*b//gcd(a,b)

def find_answer(*nums):

    #1 최대공약수
    print(reduce(gcd, nums)) #72

    #2 공약수
    a = set()
    GCD = reduce(gcd,nums)
    for i in range(1, int(GCD**0.5) +1):
        if GCD%i == 0:
            a.update({i, GCD//i})

    print(sorted(a)) #[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]

    #3 최소공배수
    print(reduce(lcm, nums)) #6434959386240

find_answer(6015240, 1507968, 4530816)

2021/10/24 18:42

Jaeman Lee

def common_divisior(data): #공배수
    sum = []
    result = []
    for cd in data:
        for x in range(1,cd):
            if cd % x == 0:
                sum.append(x)

    result = [s for s in sum if sum.count(s)==3]
    final = sorted(list(set(result)))
    return final

def gcd(data):
    return common_divisior(data)[-1]

from functools import reduce
def lcm(data):    
    return reduce(lambda x,y : x*y/gcd(data) , data)



print(common_divisior([6015240, 1507968, 4530816]))
print(gcd([6015240, 1507968, 4530816]))
print(lcm([6015240, 1507968, 4530816]))

2022/01/01 20:49

semipooh

arr=[]
for i in range(3):
    n = int(input("공략수를 구할 수를 입력하시오"))
    arr.append(n)

arr.sort()
divs=[]
#공약수 
for k in range(1,arr[0]+1):
    if arr[0]%k==0 and arr[1]%k==0 and arr[2]%k==0:
        divs.append(k)
divs.sort()
#최소공배수

def fun1 (a,b):
    if a%b ==0:
        return a//b
    else:
        return a

b=[]
k=1
while len(set(arr))!=1:
    k +=1
    while True:
        if arr[0]%k !=0 and arr[1]%k !=0 and arr[2]%k !=0 :
            break
        else:
            arr[0] = fun1(arr[0],k)
            arr[1] = fun1(arr[1],k)
            arr[2] = fun1(arr[2],k)
            b.append(k)

b += arr
max_com=1
for k in b:
    max_com *=k

print('공약수 :',divs)
print('최대공약수 : ',max(divs))
print('최소공배수 : ',max_com)

공약수부분은 쉬우니넘어가고

최소공배수는. 세수를 1이 될떄까지 약분하고 약분한 몫들을 모두곱해줘서 구했습니다

2022/01/21 05:09

양캠부부

// Rust

// 공약수 : {18, 12, 2, 1, 8, 3, 6, 72, 36, 9, 4, 24}

// 최대공약수 : 72

// 최소공배수 : 6434959386240

use std::collections::HashSet; fn multiple_numbers() {

let nums = [6015240, 1507968, 4530816];

let mut sets = vec![];
for num in nums { sets.push(divisors(num));}
let set0 = sets[0].clone();
let common_divisors = sets[1..].iter().fold(set0, |set, s| &set & s);

let num0 = nums[0];
let greatest_cd = nums[1..].iter().fold(num0, |g, n| gcd(g, *n));
let least_cm = nums[1..].iter().fold(num0, |l, n| lcm(l, *n));

println!("{:?}", common_divisors);
println!("{}", greatest_cd);
println!("{}", least_cm);

} fn divisors(num: u128) -> HashSet {

let mut set = HashSet::<u128>::new();
for a in 1..=num {
    if num % a == 0 {
        if !set.insert(a) || !set.insert(num / a) { break; } } } 
set

} fn lcm(a: u128, b: u128) -> u128 {

a * b / gcd(a, b)

} fn gcd(a_: u128, b_: u128) -> u128 {

let mut a = a_;
let mut b = b_;
if a < b {  let t = b;
            b = a;
            a = t;}
while b != 0 {  let t = a;
                a = b;
                b = t % b;}
a

}

2022/01/30 14:31

JW KIM

최소공배수는 주어진 수들로 하면 int형을 벗어나서 구해지지가 않네요.. 제가 아직 미숙해서 ㅋㅋ..

package org.javaturotials.ex;
import java.util.*;
import java.util.stream.Collectors;
class calu{
    int max=0;
    int a, b, c;
    String ab="";
    ArrayList<Integer> arr = new ArrayList<Integer>();
    void cal(int a, int b, int c) {
        this.a =a;
        this.b =b;      
        this.c =c;
        for(int i=1; i<=b; i++) {
            if(a%i==0 && b%i==0 &&c%i==0) {
                this.arr.add(i);
                if(max<i) {
                this.max=i;
            }
            }
            }
    //최대공약수 구하는 메소드
    }
    void cut() {
        double min=this.a;
        while(true) {
            if((min%this.a==0 )&&(min%this.b==0 )&&(min%this.c==0 )) {
                ab+=String.valueOf(min);
                break;
            }
            min++;
        }
    }

}

public class test {
    public static void main(String[] args) {    
        calu a1 = new calu();
        a1.cal(6015240, 1507968, 4530816);
        a1.cut();
        for(int i=0; i<a1.arr.size(); i++) {
            System.out.print(a1.arr.get(i) + " ");
        }
        System.out.print("\n" + a1.max);
        System.out.print("\n" + a1.ab);

   }
   }

2022/02/20 16:24

Kkubuck

inp= '6015240, 1507968, 4530816'
n1, n2, n3 = map(int,inp.split(', '))
gcd = math.gcd(n1,n2)
gcd = math.gcd(gcd, n3)
divisors = [x for x in range(1, gcd+1) if gcd%x ==0]

lcm = int(n1*n2/math.gcd(n1,n2))
lcm = int(lcm*n3/math.gcd(lcm, n3))

print(divisors, gcd, lcm)

2022/02/21 15:33

로만가

def divisor(num: int):
    dv = [1]
    for i in range(2, num//2 +1):
        if num % i == 0:
            dv.append(i)
    dv.append(num)
    return dv


def gcd(nums: list):
    commonDivisors = []
    dv = divisor(nums[0])
    for i in dv:
        cnt = 0
        for num in nums:
            if num % i == 0:
                cnt += 1
        if cnt == len(nums):
            commonDivisors.append(i)
    return commonDivisors[-1]


def sub_lcm(su, num):
    for n in range(2, num):
        cnt = 0
        for i in range(len(nums)):
            if nums[i] % n == 0:
                cnt += 1
        if cnt > 1:
            for i in range(len(nums)):
                if nums[i] % n == 0:
                    nums[i] //= n
            su *= n
    return su


def lcm(su):
    for i in range(len(nums)):
        nums[i] //= su
    su = sub_lcm(su, nums[0])
    su = sub_lcm(su, nums[1])
    for i in range(len(nums)):
        su *= nums[i]
    return su


nums = [6015240, 1507968, 4530816]
nums_gcd = gcd(nums)
nums_cd = divisor(nums_gcd)

print(' 공약수 : ', nums_cd)
print(' 최대 공약수: {0}'.format(nums_gcd))
print(' 최소 공배수: ', lcm(nums_gcd))

2023/08/04 14:23

insperChoi

목록으로