python-algorithm
[백준] 2061
무적김두칠
2020. 12. 18. 14:09
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import sys
import math
def checkPrime(n):
sieve=[True]*n
a=int(math.sqrt(n))
for i in range(2,a+1):
if sieve[i]:
for j in range(i+i,n,i):
sieve[j]=False
return [i for i in range(2,n) if sieve[i]==True]
p,k=map(int, sys.stdin.readline().split())
ans=0
tmp=checkPrime(k)
for i in range (len(tmp)):
if p%tmp[i]==0:
print("BAD %d"%tmp[i])
exit()
if ans==0: print("GOOD")
|
cs |
앞서 했던 문제랑 비슷합니다.
결국 소수(prime number)류의 문제는 시간 싸움이고 ,
일명 메모이제이션(memoization) 방식으로 에라토스테네스의 체 를 구현하여 풀었습니다.
반응형