[알고리즘]STEP 1-2주차 완전탐색/이분탐색(소수찾기)

👼🏻복습링크

소수찾기

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

1️⃣ 첫번째 풀이

❗ permutations 활용, 소수 판별 함수 만들기
👉🏻 소수 판별과 순열들을 하나의 문자열로 만드는 부분이 비효율적인 것 같음..

import itertools 
set=[1,2,3]
#순열
data1= itertools.permutations(set,2)  
#[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]
#조합
data2=itertools.combinations(set,2)
#[(1,2),(1,3),(2,3)]

import itertools, math

def prime(number):
    number=int(number)
    n=int(math.sqrt(number))+1
    if number<=1:
        return False
    if number==2:
        return True
    for i in range(2,n+1):
        if number%i==0:
            return False
    return True

def solution(numbers):
    answer = 0
    temp=[i for i in numbers]
    li=[]
    li_2=[]
    for i in range(1,len(numbers)+1):
        li+=list(itertools.permutations(temp,i))
    
    for i in li:
        t=''
        for j in i:
            t+=j
        t=int(t)
        if t!=0 and t not in li_2:
            li_2.append(t)
    
    for i in li_2:
        if prime(i):
            answer+=1
    return answer

1. prime(number)

• 해당 정수가 소수인지 판별하는 함수
• 입력된 정수의 제곱근을 반복문의 횟수로 지정(제곱근 이후의 수는 약수 짝에 의해 더 이상 확인할 필요가 없으므로)
• 정수가 1이하이면 False 반환
• 정수가 2이면 True 반환
• 반복문을 통해 나누어 떨어지는 수가 있다면 False 반환

2. solution(numbers)

• 반복문을 통해 numbers를 한자리 정수로 끊어 temp에 저장
• li와 li_2를 리스트로 생성
• 첫번째 for문
  - temp의 숫자 개수만큼 반복
  - permutation(temp,i)를 이용해 temp의 숫자의 순열을 생성하여 li에 저장
• 두번째 for문
  - li에 저장된 튜프들을 반복문을 통해 하나의 문자열로 만든 후 t에 저장
  • t를 정수형으로 변형
  • t가 0이 아니고 li_2에 없다면 li_2에 append(t)
• 세번째 for문
  - prime(i)를 통하여 li_2의 숫자가 소수인지 확인 후 맞다면 answer+=1

2️⃣ 두번째 풀이

❗ 다른 사람의 풀이 참고

• map 이용
• not in 대신 set 활용
  👉🏻 코드가 훨씬 짧아지고 효율성을 높일 수 있었음
  

import itertools, math

def prime(number):
    n=int(math.sqrt(number))+1
    if number<=1:
        return False
    if number==2:
        return True
    for i in range(2,n+1):
        if number%i==0:
            return False
    return True

def solution(numbers):
    answer = 0
    temp=[i for i in numbers]
    li=[]
    for i in range(1,len(temp)+1):
        li+=map(int,(map("".join,itertools.permutations(temp,i))))
    li=set(li)
    for i in li:
        if prime(i):
            answer+=1
    return answer

1. prime(number)

• 해당 정수가 소수인지 판별하는 함수
• 입력된 정수의 제곱근을 반복문의 횟수로 지정(제곱근 이후의 수는 약수 짝에 의해 더 이상 확인할 필요가 없으므로)
• 정수가 1이하이면 False 반환
• 정수가 2이면 True 반환
• 반복문을 통해 나누어 떨어지는 수가 있다면 False 반환

2. solution(numbers)

• 반복문을 통해 numbers를 한자리 정수로 끊어 temp에 저장
• li를 리스트로 생성
• 첫번째 for문
  - temp의 숫자 개수만큼 반복
  - permutation(temp,i)를 이용해 temp의 숫자의 순열을 생성후 map("".join,리스트)을 통해 순열 튜플의 숫자들을 합친 후 map(int,리스트)로 리스트의 수를 정수로 반환하여 li에 저장(중첩 map)
• li를 set으로 변환하여 중복되는 수 제거
• 두번째 for문
  - prime(i)를 통하여 li의 숫자가 소수인지 확인 후 맞다면 answer+=1

❓ 소수 판별하기

해당 문제에선 주어진 수가 특정 범위 내의 수가 아니라 사용하지 않았지만 유용하게 사용됨

에라토스테네스의 체

• 특정 범위의 수를 소수를 한번에 판별하는 방법
  - 소수를 판별할 수들을 배열에 할당
  - 2부터 시작하여 특정 숫자의 배수에 해당하는 숫자들을 차례로 지움
  (2의 배수 지우기, 3의 배수 지우기, 4의 배수(2의 배수에 해당되므로 이미 지워짐) X, 5의 배수 지우기...
  

n=100
list=[True]*(n+1)
m=int(n**0.5)
for i in range(2,m+1):
	if list[i]==True:
    	for j in range(i+i,n+1,i):
        	list[j]=False
list=[i for i in range(2,n+1) if list[i]==True]
#list에는 소수만 남게 됨