[백준] 22943번 - 수 (Python) 문제 및 풀이

문제) 백준 - 수학 - 수

https://www.acmicpc.net/problem/22943

22943번: 수

 

소수 판별을 이용해 다양한 조건을 만족하는 수의 개수를 찾는 문제였습니다. 0부터 9까지 K개로 이루어진 수를 찾기 위해 itertools에 내장된 permutation을 활용했습니다. 만약 뽑힌 수의 앞 수가 0일 경우 만족하지 않으므로 무시합니다. 그 후, 에라토스테네스의 체를 활용한 소수 판별을 바탕으로 문제에 주어진 조건대로 확인합니다.

 

Python 소스코드)

	isPrime = [True] * MAX
	def makePrime():
	isPrime[0] = False
	isPrime[1] = False
	isPrime[2] = True
	for i in range(int(math.sqrt(MAX)) + 1):
	if isPrime[i]:
	for j in range(i*i, MAX, i):
	isPrime[j] = False
	def dd(num, k):
	if num < k: return num
	while 1:
	if(num % k != 0): return num
	num //= k
	return num
	def cond1(n):
	for i in range(2, n // 2 + 1):
	if i != n - i and isPrime[i] and isPrime[n - i]:
	return True
	return False
	def cond2(n, k):
	n = dd(n, k)
	for i in range(2, int(math.sqrt(n)) + 1):
	if n % i == 0 and isPrime[i] and isPrime[n // i]:
	return True
	return False

view raw 22943.py hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/22943_%EC%88%98.py

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions