[python]메르센 소수

목적
메르센 소수를 찾는 코드를 작성합니다.

코드

Type1

import time
start = time.time()
bool = False
listPrime = []
for x in range(1,20):
    for y in range(2,int((2*x-1) ** 1/2)+1):
        if (x*2 - 1) % y == 0:
            bool = True
    if bool == False:
        listPrime.append(2*x-1)
    bool = False

for x in listPrime:
    q = 2 ** x - 1
    for y in range(2,int(q ** 1/2)+1):
        if q % y == 0:
             bool = True
    if bool == False:
        print(q)
    bool = False
print("time :", time.time() - start)

Type2

import time
start = time.time()
bool = False
for x in range(1,20):
    q = 2 ** x - 1
    for y in range(2,int(q ** 1/2)+1):
        if q % y == 0:
             bool = True
    if bool == False:
        print(q)
    bool = False
print("time :", time.time() - start)

Type3

import time
start = time.time()
bool = False
for x in range(1,20):
    q = 2 ** (2*x-1) - 1
    for y in range(2,int(q ** 1/2)+1):
        if q % y == 0:
             bool = True
    if bool == False:
        print(q)
    bool = False
print("time :", time.time() - start)하세요

설정
type1: 자연수를 차례로 넣어 확인합니다.
type2: 홀수를 차례로 넣어 확인합니다.
type3: 소수를 찾아 그 소수를 차례로 넣어 확인합니다.
(소수는 type1의 방식으로 홀수만을 넣어 찾음)

결과

type2/ type1
20 7.050
30 20.157
-> 숫자가 증가할수록 type2/type2가 큰 폭으로 증가함

type3/ type2
20 5.858
30 6.031
-> 숫자가 증가함에도 type3/type2가 크게 변하지 않음

• 30이후로는 시간이 너무 오래 걸려 측정이 힘듦
• 20 이후로 유의미한 시간차가 나타남
• 생각보다 type 1, 2의 속도 차이가 큼
  (코드 길이 차이로 인해 초반에는 type2이 빠르고 후반에는 type1이 빠를 것으로 예상했으나 초반에 계산 속도가 빨라 모두 type1이 우세)