소인수분해

[티나ㆍ스프라우..(tinaptec)]

1. 에라토스테네스의 체로 입력숫자까지 소수 구함

2. 숫자 1이 될때까지 구한 소수로 나눠나감

이거보다 빠른게 잇을까

속도 존나느린데

메모리도 많이먹고

[ㅊㄹ(59.22)]

그 무슨 정리 쓰면 검사하는 수 줄일수 잇는걸로 아는데... 수학이 필료합니다

[티나ㆍ스프라우트(tinaptec)]

아 그 소수 체크할때 2부터 루트n까지 체크하는거요?

[배트짱(rubybat)]

루트n까지 하는것보다 에라토스테네스가 훨빠르더라

[배트짱(rubybat)]

그말고 뭔 식 두개있던데

[배트짱(rubybat)]

뭔진몰라도 한개는 그냥 되는거고 한개는 리만가설 참이라고 했을때만 성립되는거

[티나ㆍ스프라우트(tinaptec)]

근데 루트n까지 체크하는건 한 숫자의 소수성을 체크하는거고 에라토스테네스는 1~n에서 소수구하는거잖음

[배트짱(rubybat)]

AKS랑 밀러-라빈판별법이구나

[배트짱(rubybat)]

얼마전에 들어만본거라 먼진잘은머름

[티나ㆍ스프라우트(tinaptec)]

검색해볼게여 ㄳ

[티나ㆍ스프라우트(tinaptec)]

어렵네

[티나ㆍ스프라우트(tinaptec)]

밀러-라빈 소수판별법은 솔직히 어떻게 유도된건지 하나도 모르겠는데 결과만 놓고보면 어메이징하네 퍄퍄