Project Euler - 004(Largest palindrome product)

사이트

영어 : https://projecteuler.net/problem=4
한글 : http://euler.synap.co.kr/prob_detail.php?id=4

문제

영문

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

한글

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

풀이과정

이번 문제는 좀 어려웠다.
대칭수를 구하는 부분에서 어떻게 해야하나 많은 고민을 했다.
처음에는 리스트를 이용해 역순정렬을 하려고 했지만, 문자열을 바로 역순으로 보여주는 문법이 있어 이를 응용했다.
(자세한 자료는 아래 참고사이트에서 확인)

내가 푼 답안

# 대칭수를 찾기 위한 함수 

def palindrome(num):

    # 넘어온 굿자를 문자열화 시킨다.(숫자는 안되기 때문...) 

    num_str = str(num)

    #print("구하고자 하는 수 : ", num_str) 



    # 대칭수인지 아닌지 판별을 위해 문자를 뒤집는다. 

    num_str_reverse = num_str[::-1]

    #print("문자를 뒤집는다. : ", num_str_reverse) 



    if num_str==num_str_reverse:

        #print("%d 는 대칭수 입니다." %num) 

        return True

    else:

        #print("%d 는 대칭수가 아닙니다." %num) 

        return False

# palindrome(9009) 



def main(n1, n2):

    lst = [0, 0, 0]

    for x in range(1, n1+1):

        for y in range(1, n2+1):

            num = x * y

            if palindrome(num)==True and lst[0] < num:

                lst[0] = num

                lst[1] = x

                lst[2] = y

    return lst



print("두자리 수의 곱 중 가장 큰 대칭 수 구하기")

num = main(99, 99)

print("대칭수 : %d\n1번수 : %d\n2번수 : %d" % (num[0], num[1], num[2]))



print("===" * 50)



print("세자리 수의 곱 중 가장 큰 대칭 수 구하기")

num = main(999, 999)

print("대칭수 : %d\n1번수 : %d\n2번수 : %d" % (num[0], num[1], num[2]))

참고사이트

• palindrome 단어 뜻
• StackOverflow - Reverse a string in Python
• Python - Extended Slices
• python list reverse
• python string reverse
• 문자열을 철자 하나씩 끊어 list로 저장하려 합니다

#Project_Euler #question4 #프로젝트_오일러 #python3 #Largest_palindrome_product #palindrome #StackOverflow #reverse #Extended_Slices

임을위한행진곡(원곡)

Project Euler - 003

Project Euler - 003(Largest prime factor)

사이트

영어 : https://projecteuler.net/problem=3
한글 : http://euler.synap.co.kr/prob_detail.php?id=3

문제

영문

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

한글

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.

풀이과정

1. 소인수가 저장될 리스트lst = []를 만든다.
2. 소인수는 2부터 시작한다.
3. 구하고자 하는 수를 2로 나누어 떨어진다면 2는 소인수이다. 그렇다면 다음 수를 구하기위해 원 수에서 x를 나누어 나온 몫을 다시 구하고자 하는 수에 넣는다.
4. 만약 나누어 떨어지지 않는다면 그 수는 소인수가 아니고 하나를 증가(x+1)시켜 다시 계산하도록 한다.
5. 제수가 피제수보다 커지면 모든 소인수를 다 구한 것이다.(더이상 나눌 수가 없음)

내가 푼 답안

lst = []         # 소인수가 저장될 리스트 

n = 600851475143 # 소인수 구할 수 

x = 2            # 최초로 나눌 수(나눠지지 않으면 +1 씩 커진다) 



'''

n(피제수 : 나누어 지는 수)이 x(제수 : 나누는 수)로 나뉘게 될 때

제수(x)가 피제수(나누어 지는 수) 보다 커지면 반복문을 종료한다.

'''

while x <= n:

    if n % x == 0:    # 피제수가 제수에 나누어 진다면 x는 n의 소인수 이다. 

        lst.append(x) # 소인수를 리스트에 추가 

        n /= x        # 피제수를 소인수로 나눈 몫을 다음 피제수로 한다. 

    else :

        x += 1        # 나누어 지지 않는다면 소인수가 아님(제수를 하나 증가시킨다) 



print(lst)

#Project_Euler #question3 #프로젝트_오일러 #python3