Summation Of Four Primes/1002

1. Approach ¶

�� 한 �� . �� 합�� 하��, 4�� 합�� 한��. �� pseudo code �� 해��.

~cpp 
for eachGenNumberFour in GenNumbersFour
  isAllPrimeNumber:
      print eachGenNumberFour
      return
print "impossible"

GenNumbersFour = 합��� x ��� ��� ���합������트

합�� x �� 합��트�� 해 �� 할�� 하��, ��트�� 트�� 4�� 합�� 한 �� n �� 하�� 할 �� . �� 해�� TDD�� 행.

~cpp 
class PrimeNumberList:
    def __init__(self,aNum):
        self.size = aNum
        self.resultTable = []
        self.createList()

    def createList(self):
        for i in range(2,self.size+1):
            if self.isPrimeNumber(i):
                self.resultTable.append(i)

    def isPrimeNumber(self,aNum):
        for eachValue in self.resultTable:
            if aNum % eachValue == 0:
                return False
        return True

    def getList(self):
        return self.resultTable

class PrimeNumberTest(unittest.TestCase):
    def testPrimeNumber(self):
        self.assertEquals([2,], PrimeNumberList(2).getList())
        self.assertEquals([2,3], PrimeNumberList(3).getList())
        self.assertEquals([2,3,5], PrimeNumberList(5).getList())
        self.assertEquals([2,3,5,7,11], PrimeNumberList(12).getList())
        self.assertEquals([2,3,5,7,11,13,17,19], PrimeNumberList(20).getList())

�� 트�� 4�� 하�� 해 ��하��. �� 해�� 허��하�� 하��. �� 허��한�� .

~cpp 
def selectionFour(aList):
    sizeOfList = len(aList)
    for i in range(sizeOfList):
        for j in range(sizeOfList):
            for k in range(sizeOfList):
                for l in range(sizeOfList):
                    yield [aList[i],aList[j],aList[k],aList[l]]

2. full source ¶

~cpp 
from __future__ import generators
import psyco

class PrimeNumberList:
    def __init__(self,aNum):
        self.size = aNum
        self.resultTable = []
        self.createList()

    def createList(self):
        for i in range(2,self.size+1):
            if self.isPrimeNumber(i):
                self.resultTable.append(i)

    def isPrimeNumber(self,aNum):
        for eachValue in self.resultTable:
            if aNum % eachValue == 0:
                return False
        return True

    def getList(self):
        return self.resultTable

def selectionFour(aList):
    sizeOfList = len(aList)
    for i in range(sizeOfList):
        for j in range(sizeOfList):
            for k in range(sizeOfList):
                for l in range(sizeOfList):
                    yield [aList[i],aList[j],aList[k],aList[l]]

def main():
    n = int(raw_input('input number : '))
    primeNumberList = PrimeNumberList(n)
    for eachPrimeNumberSeq in selectionFour(primeNumberList.getList()):
        if sum(eachPrimeNumberSeq) == n:
            print eachPrimeNumberSeq
            return
    print "Impossible"

if __name__=="__main__":
    #unittest.main(argv=('','-v'))
    psyco.full()
    main()

3. �� - 4�� . ¶

��펙�� 10000000 �� 4�� 한��. �� 해�� 해 profiling �� 해 ��.

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 10000
[2, 2, 23, 9973]
         21065 function calls in 6.387 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.075    0.075    1.201    1.201 summationoffourprimes.py:13(createList)
        0    0.000             0.000          profile:0(profiler)
        1    5.103    5.103    6.387    6.387 summationoffourprimes.py:88(main)
        1    0.000    0.000    1.201    1.201 summationoffourprimes.py:8(__init__)
     9999    1.126    0.000    1.126    0.000 summationoffourprimes.py:18(isPrimeNumber)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:24(getList)
    11061    0.083    0.000    0.083    0.000 summationoffourprimes.py:79(selectionFour)
        1    0.000    0.000    6.387    6.387 <string>:1(?)

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 50000
[2, 2, 3, 49993]
         60269 function calls in 24.926 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.428    0.428   19.348   19.348 summationoffourprimes.py:13(createList)
        0    0.000             0.000          profile:0(profiler)
        1    5.492    5.492   24.923   24.923 summationoffourprimes.py:88(main)
        1    0.000    0.000   19.348   19.348 summationoffourprimes.py:8(__init__)
    49999   18.920    0.000   18.920    0.000 summationoffourprimes.py:18(isPrimeNumber)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:24(getList)
    10265    0.083    0.000    0.083    0.000 summationoffourprimes.py:79(selectionFour)
        1    0.003    0.003   24.926   24.926 <string>:1(?)


Hit any key to close this window...

�� 테�� 하�� . �� 해��

PrimeNumber�� , ��화�� 하��. �� psyco �� 하��. �� , 10000000 �� 10��. �� 50000�� 24�� .

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 10000
[2, 2, 23, 9973]
         11067 function calls in 5.417 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1    0.000    0.000    5.417    5.417 <string>:1(?)
        1    0.000    0.000    0.013    0.013 summationoffourprimes.py:36(createList)
        1    0.000    0.000    0.013    0.013 summationoffourprimes.py:31(__init__)
    11061    0.094    0.000    0.094    0.000 summationoffourprimes.py:103(selectionFour)
        1    5.309    5.309    5.416    5.416 summationoffourprimes.py:112(main)
        1    0.013    0.013    0.013    0.013 summationoffourprimes.py:8(prime2)


Hit any key to close this window...

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 50000
[2, 2, 3, 49993]
         10271 function calls in 7.878 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1    0.002    0.002    7.878    7.878 <string>:1(?)
        1    0.002    0.002    0.090    0.090 summationoffourprimes.py:36(createList)
        1    0.000    0.000    0.090    0.090 summationoffourprimes.py:31(__init__)
    10265    0.098    0.000    0.098    0.000 summationoffourprimes.py:103(selectionFour)
        1    7.688    7.688    7.876    7.876 summationoffourprimes.py:112(main)
        1    0.088    0.088    0.088    0.088 summationoffourprimes.py:8(prime2)


Hit any key to close this window...

��화 �� 50000�� 한 �� .

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 1000000
[2, 2, 13, 999983]
         470994 function calls in 26.768 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1    0.040    0.040   26.768   26.768 <string>:1(?)
        1    0.062    0.062    2.708    2.708 summationoffourprimes.py:36(createList)
        1    0.000    0.000    2.708    2.708 summationoffourprimes.py:31(__init__)
   470988    5.244    0.000    5.244    0.000 summationoffourprimes.py:103(selectionFour)
        1   18.777   18.777   26.728   26.728 summationoffourprimes.py:112(main)
        1    2.646    2.646    2.646    2.646 summationoffourprimes.py:8(prime2)


Hit any key to close this window...

�� selectionFour �� percall �� . 하��, call 횟�� 470988 �� . �� 해�� inlining �� 하��.

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 1000000
(2, 2, 13, 999983)
         6 function calls in 16.671 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1   13.736   13.736   16.540   16.540 summationoffourprimes.py:121(main2)
        1    0.067    0.067    2.804    2.804 summationoffourprimes.py:36(createList)
        1    2.738    2.738    2.738    2.738 summationoffourprimes.py:8(prime2)
        1    0.131    0.131   16.671   16.671 <string>:1(?)
        1    0.000    0.000    2.804    2.804 summationoffourprimes.py:31(__init__)


Hit any key to close this window...

10000000 �� 해�� 7.49 �� (profiler �� 할 �� 하�� profiler �� psyco �� 행)

4. ��화 2�� : �� ¶

�� inlining �� 한 �� selectionFour ��. selectionFour �� 행�� (n �� )^4 �� . �� smart 하�� 할 �� .
�� 하�� 하�� 할 �� 하�� 한��.
�� 한 ��, 4�� 해�� 할 �� .

selectionFour �� 하��.

~cpp 
def selectionFour(aList,aNum):
    sizeOfList = len(aList)
    for i in range(sizeOfList):
        for j in range(sizeOfList):
            for k in range(sizeOfList):
                for l in range(sizeOfList):
                    expectedLastValue = aNum-(aList[i]+aList[j]+aList[k])
                    if expectedLastValue in aList:
                        yield [aList[i],aList[j],aList[k],expectedLastValue]
                    else:
                        break

inlining �� 하�� 6.4�� 하��. inlining �� 하�� 5.7�� 한��.

5. ��화 3�� : PyRex ¶

PyRex �� Python �� C �� 환해��. �� , C �� 파��하�� 행. �� 7.x ��, PsyCo �� 히�� . C �� . �� . �� 하�� 해�� 향�� 하�� .

6. 한 �� ¶

�� , 한�� 하�� 학�� .
�� 한 ��. �� 황�� , 한 �� 해�� 히 �� .

7. �� 했�� 하�� . �� ¶

PrimeNumber �� 화�� 해��. �� , �� 화�� 해�� 학��할 �� . �� 2�� 획�� .
��한 �� 화 �� , �� . �� 해�� .

SummationOfFourPrimes

Summation Of Four Primes/1002

Contents

1. Approach ¶

2. full source ¶

3. ��������� - 4��� ��������� ������ ��������� ���������. ¶

4. ������화 2��� : ������ ��������� ��������� ¶

5. ������화 3��� : PyRex ¶

6. 한 ��� ������ ��������� ¶

7. ��� 했��������� 하��� ���. ������ ¶

3. �� - 4�� . ¶

4. ��화 2�� : �� ¶

5. ��화 3�� : PyRex ¶

6. 한 �� ¶

7. �� 했�� 하�� . �� ¶