개발/코딩테스트
백준 코딩테스트 boj 5615 : 아파트 임대
ensuta
2024. 3. 17. 07:28
728x90
반응형
문제
동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수)
동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다.
동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다.
출력
첫째 줄에 있을 수 없는 아파트 면적의 수를 출력한다.
예제 입력
10
4
7
9
10
12
13
16
17
19
20
예제 출력
2
정답 코드 (Python)
#전꽃비블로그
L = [2,3,5,7,11,13,17,19,23]
def isPrime(n):
if n in L:
return True
if n == 1 or n % 2 == 0:
return False
s, d = 0, n - 1
while d % 2 == 0:
s += 1
d //= 2
for a in L:
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s):
y = pow(x, 2, n)
if y == 1 and x != 1 and x != n - 1:
return False
x = y
if x != 1:
return False
return True
n = int(input())
count_primes = 0
for _ in range(n):
c = int(input())
if isPrime(2 * c + 1):
count_primes += 1
print(count_primes)
반응형