[PYTHON] 범위가 너무 큽니다. Python

범위가 너무 큽니다. Python

숫자 x의 가장 큰 소수 요소를 찾고, 파이썬은 범위가 너무 큽니다 오류를 제공합니다. 나는 x 범위를 사용하여 시도했지만 OverflowError : Python int가 너무 커서 C로 변환 할 수 없습니다.

x = 600851475143
maxPrime = 0


for i in range(x):
    isItPrime = True
    if (x%i == 0):
        for prime in range(2,i-1):
            if (i%prime == 0):
                isItPrime = False
        if (isItPrime == True):

            if (i > maxPrime):
                maxPrime = i;

print maxPrime

해결법

1. ==============================

   1.Python의 오래된 (2.x) 버전에서 xrange는 플랫폼의 원래 긴 정수 크기에 의해 바인딩 된 Python 2.x int 만 처리 할 수 ​​있습니다. 또한, range는 파이썬 2.x에서 미리 모든 숫자를 가진리스트를 할당하기 때문에 큰 인수에 적합하지 않습니다.

   Python의 오래된 (2.x) 버전에서 xrange는 플랫폼의 원래 긴 정수 크기에 의해 바인딩 된 Python 2.x int 만 처리 할 수 ​​있습니다. 또한, range는 파이썬 2.x에서 미리 모든 숫자를 가진리스트를 할당하기 때문에 큰 인수에 적합하지 않습니다.

   3.x (권장) 또는 long int (C)가 64 비트 인 플랫폼으로 전환하거나 다음 드롭 인을 사용할 수 있습니다.

   import itertools
   range = lambda stop: iter(itertools.count().next, stop)
   

   동등하게, 일반 형식으로 :

   def range(stop):
      i = 0
      while i < stop:
          yield i
          i += 1
   

2. ==============================

   2.이것이 내가하는 일이다.

   이것이 내가하는 일이다.

   def prime_factors(x):
       factors = []
       while x % 2 == 0:
           factors.append(2)
           x /= 2
       i = 3
       while i * i <= x:
           while x % i == 0:
               x /= i
               factors.append(i)
           i += 2
       if x > 1:
           factors.append(x)
       return factors
   
   >>> prime_factors(600851475143)
   [71, 839, 1471, 6857]
   

   그것은 꽤 빠르며 그것이 옳다고 생각합니다. 발견 된 요인의 최대치를 취하는 것은 꽤 간단합니다.

   2017-11-08

   5 년이 지난 지금으로 돌아가서, 나는 수확량과 수확량을 사용하여 프라임 범위에서 더 빠르게 계산합니다 :

   def prime_factors(x):
       def diver(x, i):
           j = 0
           while x % i == 0:
               x //= i
               j += 1
           return x, [i] * j
       for i in [2, 3]:
           x, vals = diver(x, i)
           yield from vals
       i = 5
       d = {5: 2, 1: 4}
       while i * i <= x:
           x, vals = diver(x, i)
           yield from vals
           i += d[i % 6]
       if x > 1:
           yield x
   
   list(prime_factors(600851475143))
   

   dict {5 : 2, 1 : 4}는 모든 홀수를 볼 필요가 없다는 사실을 사용합니다. 위의 3에서 모든 숫자 x % 6 == 3은 3의 배수이므로 x % 6 == 1 및 x % 6 == 5 만보고 필요하며 2와 4를 교대로 추가하여 이들 사이를 건너 뛸 수 있습니다. 5 시부 터 시작합니다.

3. ==============================

   3.허용 된 대답은 xrange에 대한 드롭 인 대체를 제안하지만 하나의 사례 만 포함합니다. 좀 더 일반적인 드롭 인 대체 방법이 있습니다.

   허용 된 대답은 xrange에 대한 드롭 인 대체를 제안하지만 하나의 사례 만 포함합니다. 좀 더 일반적인 드롭 인 대체 방법이 있습니다.

   def custom_range(start=0,stop=None,step=1):
       '''xrange in python 2.7 fails on numbers larger than C longs.
       we write a custom version'''
       if stop is None:
           #handle single argument case. ugly...
           stop = start
           start = 0
       i = start
       while i < stop:
           yield i
           i += step
   
   xrange=custom_range
   

4. ==============================

   4.나는 확실히 xrange를 고집 할 것입니다. 0과 무한대에 필적하는 숫자가 메모리에 부담이되는 것처럼 보이는 목록을 작성한 이후입니다. xrange는 질문 할 때 숫자 만 생성합니다. 너무 큰 문제의 경우, "긴"시도해보십시오. 숫자 끝에 L을 쓰면됩니다. 나는 그것을 테스트하기 위해 자신의 버전을 만들었습니다. 내 컴퓨터를 사실상 잠시 (1) 루프로 파괴하지 않기 위해 작은 잠을 잤다. 프로그램이 완전히 끝나기를 참지 못해서 인쇄 진술서를 넣었습니다.

   나는 확실히 xrange를 고집 할 것입니다. 0과 무한대에 필적하는 숫자가 메모리에 부담이되는 것처럼 보이는 목록을 작성한 이후입니다. xrange는 질문 할 때 숫자 만 생성합니다. 너무 큰 문제의 경우, "긴"시도해보십시오. 숫자 끝에 L을 쓰면됩니다. 나는 그것을 테스트하기 위해 자신의 버전을 만들었습니다. 내 컴퓨터를 사실상 잠시 (1) 루프로 파괴하지 않기 위해 작은 잠을 잤다. 프로그램이 완전히 끝나기를 참지 못해서 인쇄 진술서를 넣었습니다.

   from time import sleep
   
   x = 600851475143L
   maxPrime = 0
   
   for i in xrange(1,x):
       isItPrime = True
       if (x%i) == 0:
           for prime in xrange(2,i-1):
               if (i%prime) == 0:
                   isItPrime = False
                   break
           if isItPrime:
               maxPrime = i
               print "Found a prime: "+str(i)
       sleep(0.0000001)
   
   
   print maxPrime
   

   희망이 도움이!

   편집하다: 또한이 버전을 만들기 위해 몇 가지 편집 작업을 수행했습니다. 그것은 상당히 효율적이며이 프로그램이 제공하는 꽤 많은 숫자를 확인했습니다 (지금까지 체크 아웃 한 것 같습니다).

   from time import sleep
   
   x = 600851475143L
   
   primes = []
   
   for i in xrange(2,x):
       isItPrime = True
       for prime in primes:
           if (i%prime) == 0:
               isItPrime = False
               break
       if isItPrime:
           primes.append(i)
           print "Found a prime: "+str(i)
       sleep(0.0000001)
   
   
   print primes[-1]
   

5. ==============================

   5.매우 불필요한 코드는 디바이더를 얻는 가장 좋은 방법은 아니지만 for와 range로 해봤지만 긴 변수 때문에 실행할 수 없으므로 잠시 사용하기로 결정했습니다. 혼자서 카운터를 늘리십시오.

   매우 불필요한 코드는 디바이더를 얻는 가장 좋은 방법은 아니지만 for와 range로 해봤지만 긴 변수 때문에 실행할 수 없으므로 잠시 사용하기로 결정했습니다. 혼자서 카운터를 늘리십시오.

   13195와 같은 32 비트 int의 경우 :

   # The prime factors of 13195 are 5, 7, 13 and 29.
   # What is the largest prime factor of the number 600851475143 ?
   
   i = 13195
   for j in xrange(2, i, 1):
       if i%j == 0:
           i = i/j
           print j
   

   더 긴 숫자를위한 좋은 방법 :

   # The prime factors of 13195 are 5, 7, 13 and 29.
   # What is the largest prime factor of the number 600851475143 ?
   
   i = 600851475143
   j = 2
   
   while i >= j:
       if i%j == 0:
           i = i/j
           print j
       j = j+1
   

   마지막 소수는 마지막으로 인쇄 된 값입니다.

from https://stackoverflow.com/questions/9816603/range-is-too-large-python by cc-by-sa and MIT license