simm4256   4년 전

도저히 풀이 방법이 떠오르질 않습니다.

1~k까지의 소수를 전부 구해보는것도 안되고

k+1~루트p까지는 최대범위가 10^50이니 더더욱 말이안되고..


문제에 나온 그림이 뭔가 힌트일거라 생각해서 제 나름대로 열심히 해석해보려 했으나

최대공약수가 나온다는건 알겠는데 나머진 이해가 하나도 안되네요 ㅠㅠ

myungwoo   4년 전

1 ~ K까지의 소수를 모두 구하는 방법이 왜 안되죠?

simm4256   4년 전

아아 멍청했네요 소스를 잘못 짰었나봐요

근데 이번엔 틀렸습니다가...

아무래도 double 자료형 특성때문에 틀린거같은데

big integer를 써야하나요?

myungwoo   4년 전

double을 사용하면 당연히 안되죠. double은 부동소수점으로 실수를 표현합니다. 실제로 double 자료형의 표현 범위를 보면 꽤나 넓어보일 수 있지만 당연히 공간을 64비트밖에 안쓰므로 표현할 수 있는 유효숫자의 개수가 적다고 보면 돼요.

이 문제에서는 큰 수 K가 어떤 소수 p에 의해 나누어 떨어지는지만 확인하면 되므로 Big Integer 구현이 필요가 없습니다.

관련해서는 아래 코드를 보시죠.

simm4256   4년 전

감사합니다.

알려주신 mod 함수 진짜 꿀팁이네요.

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