[알고리듬] #69 소수 찾기

[key word] 합성수, 메르센 수, 메르센 소수

파이썬 실습창을 열 수 있습니다.실습창 열기

 

소수 찾기

 

2** 82,589,933 − 1 (24,862,048자리 수)

이 숫자가 지금까지(2024년 4월) 인류가 찾아낸 가장 큰 소수라고 

The Great Internet Mersenne Prime Search(GIMPS)가 발표하였습니다 .

소수(prime number)는 1과 자기 자신 이외의 양의 약수가 없는 1보다 큰 자연수입니다.
2는 유일한 짝수 소수이며, 처음 5개의 작은 소수는 2, 3, 5, 7, 11입니다.
2와 5를 제외하면, 모든 소수의 일의 자리 수는 1, 3, 7, 9입니다.
1000 이하의 소수는 168개, 10000 이하의 소수는 1229개임이 밝혀져 있습니다.

소수가 아닌 1보다 큰 자연수는 합성수(composite number)라 합니다.
소수는 약수의 갯수가 2개인 수, 합성수는 약수의 갯수가 3개 이상인 수입니다,
1은 약수가 1개 뿐이므로 소수도 합성수도 아닙니다.

 

2보다 큰 자연수를 입력받아서,
그 자연수 이하에는 몇 개의 소수가 있는지 알아보세요.

 

1. 문제 분석

소수를 골라내기 위한 방법은 다음과 같습니다

• 소수는 1과 자기 자신 외에는 약수가 없다.
• 2부터 n의 제곱근까지의 수에 n의 약수가 없으면 n은 소수이다.
• n이 자기보다 작은 소수로 나누어지지 않으면 n은 소수이다

[참고] 메르센 소수

 메르센 소수

 

메르센 수(Mersenne number)는 2의 거듭제곱에서 1이 모자란 숫자를 가리킵니다.

지수 n에 대한 메르센 수는 M(n) = 2** n - 1 입니다.

메르센 소수(Mersenne prime)는 메르센 수 중에서 소수인 수입니다.  

현대에 알려진 매우 큰 소수들 중에는 메르센 소수가 상당히 많습니다.

큰 소수를 찾는 사람들은 메르센 소수를 주로 연구합니다.

2. 코딩 하기

2-1 방법 1

• 소수는 1과 자기 자신 외에는 약수가 없다.

이 방법으로 코딩하였습니다.

import time                       # 처리 시간 체크 예정
start=time.time()
n=100000                          # 십만 이하의 소수 개수 구함
cnt=1                             # 소수 개수. 소수 2는 미리 헤아림
for i in range(3,n+1,2):          # 3이상의 홀수
    flag=1                        # i가 소수라고 가정함
    for j in range(3,i//2+1,2):   # 3부터 자기의 반까지의 홀수로 나누어 봄
        if i%j==0:                # j가 i의 약수이면
            flag=0                # i는 소수가 아님
            break
    if flag:cnt+=1                # flag=1이면(i가 소수이면) 소수 개수 증가              
print(cnt) 
end=time.time()
run=end-start
print(run)

'''
결과는
9592
13.12797737121582

10만 이하의 소수는 9592개이며
나의 컴퓨터로 약 13.128초 걸립니다.
'''

 

 

2-1 방법 2

• 2부터 n의 제곱근까지의 수에 n의 약수가 없으면 n은 소수이다.

import time                       
start=time.time()
n=100000                          
cnt=1                             
for i in range(3,n+1,2):          
    flag=1                        
    for j in range(3,int(i*0.5)+1,2):   # 이곳만 수정. i의 제곱근까지
        if i%j==0:               
            flag=0
            break
    if flag:cnt+=1
print(cnt) 
end=time.time()
run=end-start
print(run)

'''
결과는
9592
13.03674030303955

나의 컴퓨터로 약 13.037초 걸렸습니다.
아주 조금 빨라졌습니다.
'''

 

 

2-3 방법 3

• n이 자기보다 작은 소수로 나누어지지 않으면 n은 소수이다

이 방법으로 코딩하였습니다.

import time                       
start=time.time()
n=100000                          
p=[2]                      # 2는 소수                        
for i in range(3,n+1,2):          
    flag=1                        
    for j in p:            # 이미 구한 소수들 
        if j>i**0.5:break  # j가 i의 제곱근보다 크면 소수
        if i%j==0:
            flag=0
            break
    if flag:p.append(i)    # i가 소수면 p에 모음
cnt=len(p)                 # 소수 게수 구함
print(cnt) 
end=time.time()
run=end-start
print(run)

'''
결과는
9592
0.2683877944946289

약 0.268초, 약 49배 빨라졌습니다.
알고리듬의 중요성을 다시 한 번 느낍니다.
'''

 

리스트(list)가 중요하게 사용되었습니다.

애용하여 주세요.

수고하셨습니다.

안녕!