프로젝트 오일러 47번

import math
judgement=False
def sieve(n):
    if n < 2:
        return []
    s = [0, 0] + [1] * (n - 1)
    for i in range(2, int(n**.5)+1):
        if s[i]:
            s[i*2::i] = [0] * ((n - i)//i)
    return [i for i, v in enumerate(s) if v]
def isPrime(n):
    if(n==1):
        return False
    count=0
    for i in range(2,(int)(math.sqrt(n))+1):
        if(n%i==0):
            count=count+1
    if(count==0):
        return True
    else:
        return False
arr_prime=sieve(1000)
def primeFact(n):
    arr=[]
    for i in range(0,len(arr_prime)):
        prime=arr_prime[i]
        if(n%prime==0):
            arr.append(prime)
            n=(int)(n/prime)
        if(isPrime(n)):
            arr.append(n)
            break
    arr=list(set(arr))
    arr.sort()
    return arr
arr_number=[]
arr_real=[]
for i in range(1,140000):
    if(len(primeFact(i))==4):
        arr_number.append(i)
        arr_real.append(primeFact(i))
        if(len(arr_number)==4):
            if(arr_number[0]+1==arr_number[1] and arr_number[0]+2==arr_number[2] 
               and arr_number[0]+3==arr_number[3]):
                for i in range(0,3):
                    for j in range(0,4):
                        for k in range(0,4):
                            if(arr_real[i][j]!=arr_real[i+1][k]):
                                judgement=True
                            else:
                                judgement=False
                                break
                        if(judgement==False):
                            break
                    if(judgement==False):
                        break
                if(judgement==True):
                    print(arr_number[0])
                    break
            else:
                arr_number.remove(arr_number[0])
                arr_real.remove(arr_real[0])
#반환 시간 : 59.6s

솔직히 이번 문제는 어거지로 풀었다.

일단 소수를 구할 수 있는 모든 알고리즘은 다 함수로 정의했다.

isPrime()은 소수 판정에 사용되었고

sieve()는 에라토스테네스의 체를 활용하여 소인수의 후보를 미리 리스트에 저장하는 데 사용되었다.

(출처 : http://codingdojang.com/scode/503)

primeFact()는 소인수분해를 한 결과를 리스트에 저장호 중복 제거, 오름차순 정렬을 한 후 반환해주는 함수이다.

먼저 소인수분해 결과의 리스트의 길이를 세어 4일 때 판정을 시작하도록 하였다.

연속되는 숫자인지 확인하기 위해 리스트의 길이가 4인 숫자를 또 다른 리스트에 저장하였고,

소인수분해한 결과 또한 또 다른 리스트에 저장하였다.

그러다가 연속되는 숫자인지 확인하기 위한 리스트의 길이가 4가 되면

각 요소를 비교하여 연속되는 숫자이면 리스트들을 출력하도록 하였고

그렇지 않으면 리스트의 맨 앞에 위치하는 요소를 리스트에서 제거하였다.

1부터 쭉 돌려본 결과 정답인 부분에서 처음으로 콘솔에 데이터가 출력되었는데

운좋게도 그 부분에서 모든 조건에 부합하여 정답을 낼 수 있었다.

이후 소인수분해 리스트의 각 요소를 비교하는 코드를 넣어 좀 더 나은 코드를 만들었지만

뭔가 효율적이지 않은 것 같고 시간도 1분 정도 걸렸기 때문에

더 좋은 방법을 찾아봐야 할 것이다.