fccva   5년 전

이 문제를 힘들게 풀어서 경험을 나누고자 합니다.

1. 입력받은 숫자 N에 대해서 N = 2xy + x + y 의 자연수 해가 존재하는지에 대한 문제입니다.

이를 변형하여 소수인지 아닌지 판정하는 문제로 바꿀 수 있습니다.

2. 통상적으로 알고 있는 소수판정 알고리즘(sqrt(N) 시간이 걸리는 알고리즘)을 사용하면 시간초과 됩니다.

밀러-라빈 소수판정법을 배워봅시다.

3. 구현 방법에 따라 다르겠지만, long 타입의 범위를 넘어가는 일이 생길 수 있습니다.

저는 Java로 하느라 조금 고생했는데, BigInteger를 사용하면 됩니다.

그리고 BigInteger에는 probablePrime이라는 메서드가 있다고 합니다.

댓글을 작성하려면 로그인해야 합니다.