0
나는 임의 숫자 x가 있습니다. x의 제곱근에 가까운 숫자 (즉,)를 계산하고 싶습니다. 나는 그들 모두를 찾을 필요가없고, 인자 분해 x은 비싸다. 한 번호 만 있으면 돼.일반적인 양의 비열한 수를 발견하십시오
일정한 시간이 바람직합니다.
A
답변
3
Euclidean algorithm으로 GCD를 계산할 수 있으므로 제곱근에 가까운 숫자를 사용하면 후보를 매우 빨리 찾아야합니다.
공통된 소수 p를 찾으면 다음 번에 동일한 소수로 히트 할 수 있기 때문에 공통된 요소가있는 숫자의 전체 문자열을 얻지 못할 가능성이 있습니다.
x를 나누지 않는 소수를 선택하고 루트 x에 가까운 (ish)을? – dmuir
계산 소수는 비싸다 ... – Scott
... 그리고 그들 중 많은 수가 ... "특별한"소수가 아니면. 메르 센 소수는 너무 희박합니다. x보다 작은 로그 (x)와 같은 것이 있습니다. 그러나 x보다 작은 뿌리 (x)가있는 소수의 계급이있는 경우, 멋지게 분포 된 폐쇄 형을 찾아 내면 이상적입니다. 나는 이런 해결책을 기대하고 있었다. 유클리드 알 고는 log (x)이고 임의의 수에 대한 coprimes의 분포에 대해서는 모르지만, 소수의 분포는 근근의 소수 (x)를 찾는 것이 기대된다. >> log (x) ... log (x)^2라고 생각합니다. – Scott