[Codility/Lesson12]CommonPrimeDivisors
| 1트
def solution(A, B):
count = 0
for (a, b) in zip(A, B):
gcd_value = gcd(a, b)
if gcd_value % (a / gcd_value) == 0 and gcd_value % (b / gcd_value) == 0:
count += 1
return count
def gcd(M, N):
if M == N:
return M
if M > N:
return gcd(M - N, N)
else:
return gcd(N - M, M)
- M, N의 대소 관계가 정해져있지 않기 때문에 위와 같이 해보았다
| 2트
def solution(A, B):
count = 0
for (a, b) in zip(A, B):
gcd_value = gcd(max(a, b), min(a, b))
if gcd_value % (a / gcd_value) == 0 and gcd_value % (b / gcd_value) == 0:
count += 1
return count
def gcd(N, M):
if M == 0:
return N
return gcd(M, N % M)
- gcd 함수의 방식만 바꾸었는데도 timeout은 없어졌다
- 절대 처음 방식은 사용하지 말아야지
| 3트
def solution(A, B):
# write your code in Python 3.6
count = 0
for (a, b) in zip(A, B):
ab_gcd = gcd(max(a,b), min(a,b))
a_gcd = gcd(max(a / ab_gcd, ab_gcd), min(a/ ab_gcd, ab_gcd))
b_gcd = gcd(max(b / ab_gcd, ab_gcd), min(b/ ab_gcd, ab_gcd))
a_div_gcd = a / ab_gcd / a_gcd
b_div_gcd = b / ab_gcd / b_gcd
#print(a_div_gcd, b_div_gcd)
if a_div_gcd == 1 and b_div_gcd == 1:
count += 1
return count
def gcd(N, M):
if M == 0:
return N
return gcd(M, N % M)
- 한번 더 나눈 결과를 사용했는데 같았다
| 4트
def solution(A, B):
# write your code in Python 3.6
count = 0
for (a, b) in zip(A, B):
ab_gcd = gcd(max(a,b), min(a,b))
a /= ab_gcd
b /= ab_gcd
a_gcd , b_gcd = ab_gcd, ab_gcd
while a_gcd != 1:
a_gcd = gcd(a, a_gcd)
a /= a_gcd
while b_gcd != 1:
b_gcd = gcd(b, b_gcd)
b /= b_gcd
if a == 1 and b == 1 :
count += 1
return count
def gcd(N, M):
if M == 0:
return N
return gcd(M, N % M)
- 최대공약수가 1이 될 때 까지 진행했더니 성공했다
Author And Source
이 문제에 관하여([Codility/Lesson12]CommonPrimeDivisors), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@zzarbttoo/CodilityLesson12CommonPrimeDivisors저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)