있습니다 많은 Atkin의 체보다는 인수에 더 기술. 예를 들어 5893을 고려하고 싶다고 가정하자. sqrt는 76.76이다. 이제 우리는 5893을 제곱의 곱으로 쓰려고한다. 음 (77 * 77-5893) = 36은 6 제곱이므로 5893 = 77 * 77-6 * 6 = (77 + 6) (77-6) = 83 * 71입니다. 그래도 문제가 해결되지 않으면 78 * 78-5893이 완벽한 사각형인지 확인했을 것입니다. 등등. 이 기술을 사용하면 개별 소수를 테스트하는 것보다 n의 제곱근 근처의 요인을 훨씬 빠르게 테스트 할 수 있습니다. 큰 소수를 체와 함께 배제하기 위해이 기술을 결합하면 체만 사용하는 것보다 훨씬 더 나은 팩토링 방법을 사용할 수 있습니다.

그리고 이것은 개발 된 수많은 기술 중 하나 일뿐입니다. 이것은 매우 간단한 것입니다. 타원 곡선을 기반으로하는 팩토링 기술을 이해하기에 충분한 수의 이론을 배우려면 오랜 시간이 걸립니다. (나는 그것들이 존재한다는 것을 안다. 나는 이해하지 못한다.)

따라서 작은 정수를 다루지 않으면 직접 그 문제를 해결하려고하지 않습니다. 대신 이미 이미 매우 효율적인 솔루션이 구현 된 PARI 라이브러리 와 같은 것을 사용하는 방법을 찾으려고 노력했습니다 . 그것으로 약 .05 초에 124321342332143213122323434312213424231341과 같은 임의의 40 자리 숫자를 고려할 수 있습니다. (당신이 궁금한 경우 인수 분해는 29 * 439 * 1132 * 157907 * 284749 * 33843676813 * 4857795469949입니다. Atkin의 체를 사용하여 이것을 파악하지 못했다고 확신합니다.)

답변

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    if (x == 1) return 1;

    for (int i = 1; i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

def divisors(n):
    count = 2  # accounts for 'n' and '1'
    i = 2
    while i ** 2 < n:
        if n % i == 0:
            count += 2
        i += 1
    if i ** 2 == n:
        count += 1
    return count