프로젝트 오일러 58번

import math
def isPrime(n):
    count=0
    for i in range(2,(int)(math.sqrt(n))+1):
        if(n%i==0):
            return False
    return True
number=1
sum=0
count_sosoo=0
for i in range(1,1000000000):
    all=i*4-3
    arr=[]
    count=((i*2-1)-1)*4
    if(count==0):
        count=1
    for j in range(0,count):
        arr.append(number)
        number=number+1
    matrix=i*2-1
    if(matrix==1):
        continue
    index1=matrix-2
    index2=index1+matrix-1
    index3=index2+matrix-1
    index4=index3+matrix-1
    if(isPrime(arr[index1])):
        count_sosoo=count_sosoo+1
    if(isPrime(arr[index2])):
        count_sosoo=count_sosoo+1
    if(isPrime(arr[index3])):
        count_sosoo=count_sosoo+1
    if(isPrime(arr[index4])):
        count_sosoo=count_sosoo+1
    if(count_sosoo/all<0.1):
        print(matrix)
        break
#반환 시간 : 154.8s

이전에 이것과 비슷한 문제가 있어서 참고했는데 알고리즘 자체로는 거의 동일했다.

하지만 생각보다 경우가 많이 나왔고

계속 행렬 형태로 만들다 보니 에러가 떠서 계산에 사용한 부분은 remove() 시켜주었고

이렇게 메모리 에러를 해결할 수 있었다.

하지만 시간이 정말 많이 걸렸다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

remove와 append가 필요 없게 코드를 다시 짜고 소수 판별 함수를 조금 손봤더니

90초를 줄일 수 있었다.

여전히 오래 걸린다.