k진수에서 소수 개수 구하기
양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
0P0처럼 소수 양쪽에 0이 있는 경우
P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
P처럼 소수 양쪽에 아무것도 없는 경우
단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.
제한 사항
1 ≤ n ≤ 1,000,000
3 ≤ k ≤ 10
입출력 예
| n | k | result |
|---|---|---|
| 437674 | 3 | 3 |
| 110011 | 10 | 2 |
나의 풀이
진수로 변환된 수를 리스트에 넣어 순회시킴
0이 아니라면 prime에 저장, 0이라면 컴마(,)로 분리
공백을 제거하기 위해 filter 사용
나온 리스트를 Prime_number() 를 사용해서 판별
하는 거였는데 1,11,12,14,15,16 시간초과
def solution(n, k):
def prime_number(n):
if n < 2:
return False
for i in range(2, n):
if i % n == 0:
return False
return True
# if num < 2:
# return False
# for i in range(2, int(num ** 0.5) + 1):
# if num % i == 0:
# return False
# return True
answer = []
prime = ''
num = []
rev_base = ''
while n > 0:
n, mod = divmod(n, k)
rev_base += str(mod)
k_num = list(rev_base[::-1] )
# 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력
print(k_num)
for i in range(len(k_num)):
if k_num[i] != '0':
prime += k_num[i]
else: #0이라면
prime += ','
num.append(prime.split(','))
filtered_list = [int(item) for item in num[0] if item.strip()]
for i in filtered_list:
if prime_number(i):
answer.append(i)
return len(answer)
개선된 코드
prime_number() 함수에서 소수 찾는 for문을 아래로 바꿔주니 바로 통과
for i in range(2, int(number**(0.5))+1):
그냥 소수 찾을 때는 다른거 쓰지말고 저것만 써야겟다 🥹
def solution(n, k):
# def prime_number(n):
# if n < 2:
# return False
# for i in range(2, n):
# if i % n == 0:
# return False
# return True
def prime_number(number):
if number==1:
return False
for i in range(2, int(number**(0.5))+1):
if number%i==0:
return False
return True
answer = []
prime = ''
num = []
rev_base = ''
while n > 0:
n, mod = divmod(n, k)
rev_base += str(mod)
k_num = list(rev_base[::-1] )
# 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력
for i in range(len(k_num)):
if k_num[i] != '0':
prime += k_num[i]
else: #0이라면
prime += ','
num.append(prime.split(','))
filtered_list = [int(item) for item in num[0] if item.strip()]
for i in filtered_list:
if prime_number(i):
answer.append(i)
return len(answer)TIL
n진수
print(bin(11)) # 2진수
print(oct(11)) # 8진수
print(hex(11)) # 16진수n진수 → 10진수
int(string, base)
print(int('101',2)) #2진수 101을 10진수로
print(int('202',3)) #3진수 202를 10진수로
print(int('303',4))
print(int('404',5))
print(int('505',6))
print(int('ACF',16))10진수 → n진수
n진수를 만드는 것은 (10진수 수/ n)으로 한 모든 나머지들의 연결
def solution(n, q):
rev_base = ''
while n > 0:
n, mod = divmod(n, q) # 몫, 나머지
rev_base += str(mod) #나머지만 이어서
return rev_base[::-1]
# 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력
print(solution(45, 3))prime_number(소수)
소수 나오면 무조건 sqrt 사용!
1보다 크고 자기 자신과 1 이외의 다른 어떤 양의 정수로도 나누어지지 않는 양의 정수 (i.e 11, 13)
def prime_number(number):
if number==1:
return False
for i in range(2, int(number**(0.5))+1):
# int(sqrt(number)+1)
if number%i==0:
return False
return True리스트 공백 제거 strip()
모든 요소에 적용시킬 때 ->리스트 컴프리헨션
strip()은 문자열의 양쪽 끝에서 지정한 문자들을 제거하는 데 사용
주로 문자열의 앞뒤 공백 문자(스페이스, 탭, 개행문자 등)를 제거하는 데 많이 사용
original_list = ['apple', 'banana', '', 'cherry', ' ', 'date']
filtered_list = [item for item in original_list if item.strip()]
# 각 요소에 제거해야할 공백 문자가 있다면
print(filtered_list)
# 출력: ['apple', 'banana', 'cherry', 'date']
