[TIL] 알고리즘: 소수 찾기 공부

추천(?)받은 소수찾기 문제

 

이걸 풀면 대부분의 소수문제는 풀 수 있을 거란 말에 호기롭게 도전하여 토욜을 소수와 함께 보냈도다,,

하드코어 코딩테스트... 끝까지 풀이하지 못했지만 오늘 공부한 부분을 기록한다.

 

- 문제 분석, 해석과 풀이 과정 기록 -

 

#프로그래머스 연습 : 소수찾기

# 한 자리 숫자가 적힌 종이조각들.. 붙여서 소수를 몇개 만들 수 있을까?

# 문자열 numbers는 0, 1, 2, 3, 4, 5, 6, 7, 8 ,9 중 랜덤개가 들어있는 문자열

# numbers는 7자리까지.

 

 

"""

입력: "17"

출력: return 값이 3   (= 7, 17, 71)

 

입력 "011" 이면

출력 : 2 (11, 101 , 011은 11이다.) 

 

 

1) 풀이를 생각해보자

소수란 무엇인가 : 1과 자신만을 약수로 가지는 수

 

-1 문자열을 숫자배열로 변환

 

-2 배열의 숫자들로 만들 수 있는 경우의 수 배열 만들기

 

-3 배열에서 2로 나누어져서 나머지가 남는지 안남는지 걸러내기

 

-4 자신보다 작은 소수로 나누어지는지 확인  =>>이 과정에서 막혔다.

예를 들어 71이 주어진다고 할때 71 아래의 숫자로 싹 나누어주면 너무 오래걸리니까..

71아래의 소수로 나누어주도록 해야겠다.

 

-5 결과값을 len()혹은 count로 세어 소수 개수 출력하기?

"""

 

 

>>>   https://school.programmers.co.kr/learn/courses/30/lessons/42839

from itertools import * #itertools로 순열 찾기

numbers = "011"

# -1 문자열을 숫자배열로 변환
numbers_list = list(numbers)  #[0, 1, 1] =>아래에서 join을 쓰기 위해 map(int, numbers)를 다시 numbers로 변경
#print(num_list) # ['0', '1', '1']

# -2 배열의 숫자들로 만들 수 있는 경우의 수 배열 만들기
def find_num(numbers_list):
    num_tuple_list = list(permutations(numbers_list))  # [('0', '1', '1'), ('0', '1', '1'), ('1', '0', '1'), ('1', '1', '0'), ('1', '0', '1'), ('1', '1', '0')]    

    # 여기서 튜플을 언패킹, join으로 합쳐주기 + # int로 바꾸어주기 + if문 으로 중복 제거
    num_list = [] 
    for i in range(len(num_tuple_list)):
        number = int(''.join(num_tuple_list[i]))  # ['011', '011', '101', '110', '101', '110']
        # 중첩 값 제거
        if number not in num_list:
            num_list.append(number)
        else:
            pass
    print(num_list) # [11, 101, 110]
        
# 에라토스테네스의 체를 써서 검증해보자

    return num_list

 

중복 제거를 할때는 set(num_list) 를 하면 된다는 정보를 보았는데,

set함수로 제거해볼까 했는데 집합으로 dict로 바꾼(?) 결과가 출력되어서 if문으로 걸러주는 것으로 변경했다.  이거까지 바라진 않았어 {}

print(set(numbers))
# 결과 {11, 101, 110}

 

3번까지 어찌저찌 하다가 4번에서... 

휴...한계를 맞이하고 소수찾기에 대한 공부를 했다

 

 

 

 

 

 

소수 구하는 코드 예제 보고 내가 어디까지 아는지 점검.

소수를 구할 때 약수를 구하기 위해 자기자신 보다 작은 수로 쭉 나누어보아야하는 것

하지만 너무 계산이 늘어질테니 (시간복잡도 상승) 소수로 나누어보면 좋겠다는 점 까지는 생각이 든다.

 

이것은 수학적 개념과 지식이 부족한 것이라 생각되어..ㅠㅠ  여러 문서들을 찾아보았다

 

공부하기

[참고] : https://veggie-garden.tistory.com/17

[참고] : https://namu.wiki/w/에라토스테네스의%20체

 

 

 

 

 

 

 

1) 일반 함수로 소수 구하는 코드 짜기

 

def is_prime_slow(number):
    #input은 전체 자연수 < 100만 
    #output은 소수
    if number == 0 or number == 1:
        return "False지롱"
    elif number == 2:
        return True
    #print(f"숫자: {number}")
    
    count_zero = 0
    for n in range(2, number):
    	# 1보다 크고 자기자신보다 작은 수로 나누어지는가
        #print(f"숫자: {number}")
        #print(f"이건 n: {n}")
        if number % n == 0:
            count_zero += 1
        
    print(count_zero)

 

 

>>> 위의 count_zero 부분부터 코드를 정리해서 한줄로 만든 코드..

# 적어두고 두고두고 보자

count_zero = sum([1 if number % n == 0 else 0 for n in range(2, number)])
return count_zero == 0

return all([number % n != 0 for n in range(2, number)]) # 전부다 약수가 아니면 True

 

 

 

 

 

 

 

2) 에라토스테네스의  체.. 를 읽어보고 구현해보기

=> 이거 아직은 어려웠다ㅠ.ㅠ 힌트 없었으면 못했을듯. 이래서 페어프로그래밍을 하는구나 싶고..

 

1차

array = [2, 3, 5, 7]

def is_prime(number):
    if number == 0 or number == 1:
        return False
    for i in range(len(array)):
        if number % array[i] == 0:
            break
        elif number % array[i] != 0:
            if number not in array:
                array.append(number)     
        # for문에서 한 번 검증 후 추가하는 상태 = 짝수만 거른 후 바로 홀수를 추가하고 있는 문제가 있다!
    return array

for i in range(0, 20):
    print(is_prime(i))

 

틀린부분은 고쳐야지...

 

 

=> 힌트 : for문이 돌고 append를 할 수 있게 변경한다

 

2차

array = [2, 3, 5, 7]

def is_prime(number):
    if number == 0 or number == 1:
        return False
    for i in range(len(array)):
        if number % array[i] == 0:
            return False
        # elif number % array[i] != 0:  => 이부분은 쓸모가 없음!
        #    continue

    # for문이 다 돌고나서 appned를 할 수 있게
    if number not in array:
        array.append(number)

for i in range(0, 20):
    print(is_prime(i))

 

 

 

---

정말... 정말 쉽지 않다.

인생에서 처음 들어본 수학적 개념을 3일만ㅋ에 공부하게 되다니 정말 놀라운 현재...

그리고 울고웃는 약 6시간 함께 해준 빛빛빛님 정말 감사합니다... 빛이 아닐리없다

 

어떤 개념인지는 이해를 했지만 체득하기에는 시간이 앞으로도 많이 필요할 것 같다.

공부... 해야지....

TIL을 쓰기에는 부족하지만 코드를 남겨두고 두고두고 보기 위해 기록한다ㅠㅠ