자료구조 스터디 4주차

4-1)

소수 구하기

 

핵심 이론

소수: 1과 자기 자신 외 약수가 존재하지 않는 수

 

기본 원리

에라토스테네스의 체:
1. 구하고자 하는 범위만큼 1차원 배열 생성

2. 2부터 시작하고 현재 숫자가 지워지지 않을 때 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움.이때 처음 선택한 숫자는 지우지 않는다.

3. 배열의 끝까지 반복해준 후 배열에남아 있는 모든 수 출력

이중 for문을 사용하므로 시간 복잡도는 N^2

최적화 정도에 따라서 실제 속도는 n(log(logn))임.

배수 삭제 과정에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문

에라토스테네스의 체는 소수를 구하는 일반적 방법으로 이용된다.

 

 

4-2)

오일러 피

자주 등장하지는 않음

오일러 피 함수 p(n)의 정의는1부터 n까지의 숫자중  n과 서로소인 자연수의 개수를 뜻함.

ex: p[6]은 1에서부터 6까지 범위에서 6과 서로소인 자연수의 개수.

서로소: 공약수가 1 외에 없는 숫자

3은 2와 서로소 

4는 6과 서로소가 아님

...

 

오일러피 핵심 이론

1. 구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스로 초기화.

2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 선택된 숫자의 배수에 해당하는 수를 배열에 끝까지 탐색하며 p[i]=p[i]-p[i]/k 연산을 수행한다.

3. 배열 끝까지 2번을 반복해 오일러피 함수를 완성한다.

 

p[i]=p[i]-p[i]/k

 

인덱스:1,2,3,4,5,6,7...12

값       :1,2,3,4,5,6,7...12

2부터 시작

2의 배수에 대해 연산 진행>>중복 삭제를 막기 위한 방법

2<=2-(2/2) ==1   // 1은 2와 서로소

4<=4-(4/2)

6<=6-(6/2) ==3

...

수행

 

다음 3에 대해 식 수행

 

인덱스와 값이 같은 수. 즉 소수인 경우에만 연산 진행

앞서 4번 인덱스의 값이 변경 됐으므로 4는 소수가 아니라 연산을 진행하지 않음.

 

3<=3-(3/3)  ==2 // 1, 2 는 둘 다 3 과 서로소

6<=3-(3/3) 인덱스 번호가 아닌 인덱스에 저장된 값으로 식 수행

9<=9-(9/3)  == 6

12<=6-(6/3)

 

끝까지 수행하면 오일러 피가 구해짐.

 

 

 

 

 

 

 

 

4-3)

유클리드 호제법

 

두 수의 최대 공약수를 구하는 알고리즘

mod연산을 이해하고 있어야함

mod연산: 두 값을 나눈 나머지를 구하는 연산 

10mod 4 = 10%4 = 2

 

mod연산으로 구현하는 유클리드 호재법

 

1.큰 수를 작은 수로 나누는 mod연산 수행

2.작은수와 mod연산을 해서 나온 값을 mod연산

3.반복하다가 나머지가 0이 되는 순간 작은 수를 최대 공약수로 설정

 

gcd(270,192)=6

 

4-4)

실전문제

최소 공배수 구하기

 

자연수 a와 b가 주어졌을 떄 두 수의 최소 공배수를 구하는 프로그램 작성

 

첫줄: 테스트 케이스의 개수를 입력받는다

테스트 케이스 입력받는다

 

각 케이스의 최소공배수를 구한다

 

유클리드 호제법을 이용해 최대공약수를 구한 후 두 수의 곱에서 최대 공약수를 나눠주는 것으로 문제 해결 가능.

 

 

 

t=int(input())
    
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
    
for i in range(t):
    a,b=map(int,input().split())
    result=(a*b)/gcd(a,b)
    print(int(result))
    print("\n")