11689번 - GCD(n, k) = 1
사랑하는 성님들... 푸신 분들 반례 정중하게 부탁드립니다...
에라토스테네스 체를 구할 때, 약수 조건까지 끼워넣어 소인수들을 구한 다음에
오일러 피함수를 이용했는데... 대체 왜..왜...왜...
틀렸습니다만 20번은 보았습니다...
반례부탁드리겠습니다..ㅠㅠ
틀렸습니다 이전에, n이 10**12까지 가기 때문에 4줄처럼 할 수 없습니다.
list l를 10**12 만큼 생성할 수 없다는 말씀이신가요 ㅠㅠ?
그럼 loop를 sqrt(n)까지 돌리는 수 밖에 없나요???ㅠㅠ
10**12는 테라바이트 단위입니다. sqrt 시간/공간에 풀 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
sdsdsf 6년 전
사랑하는 성님들... 푸신 분들 반례 정중하게 부탁드립니다...
에라토스테네스 체를 구할 때, 약수 조건까지 끼워넣어 소인수들을 구한 다음에
오일러 피함수를 이용했는데... 대체 왜..왜...왜...
틀렸습니다만 20번은 보았습니다...
반례부탁드리겠습니다..ㅠㅠ