알고리즘 문제풀이 - 소수구하기 & 기수 (Python)

1. 소수구하기

자연수 n의 소수는 n의 제곱근이하의 어떤 소수로도 나누어 떨어지지 않는 수이다.

#소수를 구하는 프로그램

def program(n):
    prime = [2, 3]  # 얻은 소수

    i = 5
    while i <= n:    
    # 2와 3을 제외한 5부터 1000까지의 수 중 소수를 체크
    
        flag = False    
        # 나누어 떨어지는 수가 있는지 확인할 Bool 변수
    
        index = 1
        while index < len(prime) and prime[index] * prime[index] <= i:
            # 현재까지 얻은 소수(prime[index])를 제곱한 숫자가 현재 체크하는 수(i) 이하이면 
            
            # 얻은 소수들 중 나누어떨어지는 수가 있는지 체크
            if i % prime[index] == 0 :  
            	#만약 나누어 떨어진다면 flag를 True로 변경하고 반복을 중단.
                flag = True
                break
                
            index += 1
        
        if flag == False:   
        # 모든 얻은 소수를 체크한 후에도 flag가 False이면 얻은 소수에 추가.
            prime.append(i)

        i += 2 
        # 짝수 제외

    for number in prime:
        print("{0}".format(number), end = " ")

program(1000)

#2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

 

2. 기수

#기수 변환 프로그램

def program(number, n):
   
    dchar = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "A", "B", "C", "D", "E", "F"]

    digit = number
    answer = ""

    while(digit != 0):
        remain = dchar[digit % n]
        answer+=str(remain)

        print("{0}|\t{1:2d}...{2}".format(n, digit, remain))

        digit = digit // n
        print(" +--------")
    print("  \t{0:2d}".format(0))
    print("10진수 {0}은 {1}진수로 {2}입니다.".format(number, n, answer))
    print()

while(True):

    number = input("변환하는 음이 아닌 정수 :")
    n = input("어떤 진수로 변환할까요?(2~16) :")

    if int(n) > 16 :
        print("{0}진수로 변환할 수 없습니다. 16이하로 입력하세요.".format(n))
        continue
    else :
        program(int(number), int(n))
        
# 변환하는 음이 아닌 정수 :58
# 어떤 진수로 변환할까요?(2~16) :2
# 2|      58...0
#  +--------
# 2|      29...1
#  +--------
# 2|      14...0
#  +--------
# 2|       7...1
#  +--------
# 2|       3...1
#  +--------
# 2|       1...1
#  +--------
#          0
# 10진수 58은 2진수로 010111입니다.

# 변환하는 음이 아닌 정수 :60
# 어떤 진수로 변환할까요?(2~16) :17
# 17진수로 변환할 수 없습니다. 16이하로 입력하세요.
# 변환하는 음이 아닌 정수 :