소수 찾기 알고리즘

소수 찾는 알고리즘은 매우 많다 그 중에서 기본적인것은 자연수 n이 주어진다면 n이 소수인지 판별하기 위해 2~n-1까지 모든 숫자를 for 문을 통해서 나누어본다 나머지가 0이 나오는 값이 없다면 그 숫자는 소수이다

위 방법이 기본적인 소수를 찾는 방법이지만 프로그래밍에서 숫자 하나당 n-3번 반복해야하기 때문에 시간이 매우 많이 소요된다

 

 

소수 찾기 n/2

자연수 n을 소수인지 확인하고 싶을 때 n번의 반복이 아니라 n/2번의 반복으로 그 값이 소수인지 판별할 수 있다

def primnumber(n):
    if n == 1: #	1은 소수가 아니므로 제외
        return False
    for i in range(2,int(n/2)+1):
        if n % i == 0:# 하나라도 나눠진다면 n는 소수가 아니다
            return False  
    return True

n번 확인하는것이 아니라 n/2+1번 반복하는 이유는 n을 나눴을때 나머지가 0이 나오는것을 확인해야 하는데 n/2보다 크면 그 수중에서 어떤수로고 n을 나눴을때 나머지가 0이 나올 수 없기 때문이다 따라서 n/2까지만 n을 나눠봐도 n이 소수인지 파악 할 수 있다 시간 복잡도 O(n)

소수를 판별할 때 n/2까지만 확인하면 된다

 

 

 

소수 찾기 √N

n/2를 이용한 방법으로 n을 50 이라고 가정한다면 약수는 1,2,5,10,25,50이 존재한다 이를 짝대로 정렬하면 1:50, 2:25, 5:10 √50의 값은 약 7.xxxx가 나온다 약수를 보면 약수의 중간값은 √50이 된다 n/2의 원리처럼 √N 까지만 확인한다면 이후 값은 확인 할 필요가 없어진다 시간 복잡도 O(√n)

def primnumber(n):
    if n == 1: #	1은 소수가 아니므로 제외
        return False
    for i in range(2,int(sqrt(n)+1)):
        if n % i == 0:# 하나라도 나눠진다면 n는 소수가 아니다
            return False  
    return True

 

 

 

에라토스테네스의 체

에라토스테네스의 체는 범위에서 소수를 구할때 매우 유용한 방법이다 1~120중에서 소수를 찾는다라고 가정한다

출처 https://ko.wikipedia.org/wiki/에라토스테네스의_체

위 사진과 같은 방식으로 소수가 아닌 수를 제거하는 방법이다

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다

√120은 약 11이기 때문에 11의 배수까지만 계산해도 그 구간에서의 소수는 모두 찾을 수 있다llm

import sys 
from math import *
input = sys.stdin.readline

def eratos(N):
    line = [0 for _ in range(N+1)]
    line[0] = 1
    line[1] = 1
    max = int(sqrt(N))+1
    for i in range(2,max):
        for k in range(i+i,N+1,i):
            line[k] = 1
    return line

line1 = eratos(120)
for i in range(2,121):
    if line1[i] == 0:
        print(i)

시간복잡도 O(NloglogN)