白駿2960エラ菌体

1100 ワード

最も有効な小数アルゴリズムで知られるエラトネス体問題.
考えは問題の説明によく表れている.
n, k = map(int,input().split() )


numbers = set() # 2 부터 n까지의 숫자 저장 
primes = [] 
removed = [] 

for i in range(2,n+1):
    numbers.add(i)


def isPrime(n):
    count = 0
    for i in range(1,n+1):
        if ( n % i == 0): # 나누어 떨어지는 경우
            count +=1 
    if (count == 2): # 1과 자기 자신으로만 나누어 떨어진다면 소수이다
        return True
    else:
        return False

i = 0
while(numbers): # 모든 숫자가 지워질 때 까지 
    if (  isPrime(i) ): # i가 소수인경우 
        primes.append(i)
        remover = i
        while( True):
            if ( remover > n ): # n을 초과한 경우 
                break # 루프 탈출
            elif ( remover in numbers): # n을 초과하지 않았고, 지워지지 않은경우
                removed.append(remover) # 삭제된 내역 저장 
                numbers.remove(remover) # 삭제한다 
            remover += i # 배수화
    i+=1 

print(removed[k-1]) # k 번째 지워진 내용 출력
        

エラーの原因:なし