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)
반응형
'개발 > 코딩테스트' 카테고리의 다른 글
코드업(codeup.co.kr) 1542 : 함수로 prime 또는 composite 출력하기 해설 (C언어) (0) | 2022.11.01 |
---|---|
코드업(codeup.co.kr) 1550 : 함수의 양의 제곱근의 정수 부분만 리턴하기 해설 (C언어) (0) | 2022.11.01 |
코드업(codeup.co.kr) 1210 : 칼로리 계산하기 해설 (C언어) (1) | 2022.05.02 |
코드업(codeup.co.kr) 1180 : 만능 휴지통 해설 (C언어) (0) | 2022.05.01 |
코드업(codeup.co.kr) 1205 : 최댓값 해설 (C언어) (0) | 2022.05.01 |