[python_파이썬_pass_에라토스테네스의체 알고리즘]백준_4134번_다음 소수_풀이

2024. 5. 19. 12:18코드리뷰

728x90
반응형

공부하는허딩크 : https://www.youtube.com/live/KtmItpIeYu4?feature=shared

 

소수판별 알고리즘을 알고 있으면 쉽게 풀 수 있다.

<첫번째 시도 : 맞았습니다. : 시간복잡도 : O(루트 n), 공간복잡도 : O(1)>

import sys
input = sys.stdin.readline

def prime(n):
    if n <= 1:
        return 0
    elif n <= 3:
        return 1
   
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return 0
    return 1
   
n = int(input())

for _ in range(n):
    num = int(input())
    while not prime(num):
        num += 1
    print(num)

 

 

<두번째 시도 : 시간초과>

처음 문제설명에는 루트 N까지만 나눠서 소수를 판별하는 문제로 소개되어 있다.

보통의 소수판별을 할때는 해당 숫자의 제곱근까지만 해도 소수로 판별하는데 문제가 없는 것은 알고리즘 자체로 알고 있다. 혹시 몰라 제곱근이 아니라 전체 수를 해서 코드를 조금 수정해서 해봤는데 역시나 시간초과가 뜬다.

import sys
input = sys.stdin.readline

def prime(n):
    if n <= 1:
        return 0
    elif n <= 3:
        return 1
   
    for i in range(2, n):
        if n % i == 0:
            return 0
    return 1
   
n = int(input())

for _ in range(n):
    num = int(input())
    while not prime(num):
        num += 1
    print(num)

 

<소수판별 알고리즘>

처음 파이썬을 공부할때 소수 판별하는 문제를 자주 접할 수 있다. 그래서 한번 마음 먹고 정리를 해서 어떻게 구현하는지 대략 머릿속에 담아놨다. 

주어진 정수가 1보다 같거나 작은 경우 무조건 False가 나오도록 return 0을 만들어 주고 2와 3은 소수니까 return 1로 지정해준다.

그 다음 4부터 for문에 적용되서 소수를 판별하는데 2부터 int(n**0.5) + 1까지의 범위중에 n을 나누었을때 나머지가 0이 된다는 것은 1과 자기 자신을 제외한 어떤 수에 의해서 나누어 떨어진다는 의미이다.

그래서 나누어 떨어질때 return 0으로 False를 지정했다.

그리고 n이 for문에서 한번도 return 0이 걸리지 않는 다는 건 소수라는 의미기 때문에 for문이 끝나고 바로 return 1을 설정해주면 해당 알고리즘은 종료된다.

 

1. 에라토스테네스의 체 알고리즘 : 고대 그리스의 수학자 에라토스테네스가 고안한 소수를 찾는 효율적인 알고리즘.

주어진 범위 내의 모든 소수를 빠르게 구하는데 사용된다. 이 알고리즘의 핵심 아이디어는 소수가 아닌 수를 반복적으로 지워 나가는 방식으로 소수를 찾는 방식이다.

하나의 정수를 소수판별하는게 아닌 범위의 정수를 판별하는데 조금 더 유용하다.

 

결과 : is_prime = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0]


#에라토스테네스의체 알고리즘 : 구간의 소수판별하는데 유용
N = 20

def Prime(num):
    is_prime = [1] * (num + 1) #모든 수를 소수라고 가정
    is_prime[0] = is_prime[1] = 0 #0 과 1은 소수가 아니니까 바로 아니라고 바꿔줌
   
    p = 2
    while (p * p <= num): #제곱급까지로 지정해서 효율성 높임
        if is_prime[p]:
            for i in range(p * p, num + 1, p): #배수를 걸러줌
                is_prime[i] = 0 #각 숫주의 배수는 False로 설정
        p += 1
   
    prime_numbers = [p for p in range(num + 1) if is_prime[p]] #결과적으로 True로 남아 있는 인덱스가 소수를 나타냄
   
    return prime_numbers

print(Prime(N))
   
#range(4, 21, 2)=> 4, 6, 8, 10, 12, 14, 16, 18, 20
#range(9, 21, 3)=> 9, 12, 15, 18
#range(16, 21, 4)=> 16, 20
#기존 2~21까지 True였다가 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20까지 False로 변경

 

시간복잡도 : O(n log log n)

공간복잡도 : O(n)

 

2. 하나의 정수일때 효율적인 소수 판별 (내 코드보다 더 효율적임>

1) 정수의 숫자가 주어졌을때 1보다 같거나 같으면 return 0

2) 2와 3일 경우 return 1

3) 2의 배수이거나 3의 배수면 return 0

4) 소수의 형태

  • 6k: 6의 배수는 소수가 될 수 없습니다(6 자체도 소수가 아닙니다).
  • 6k + 2: 이는 짝수이므로 소수가 아닙니다(2를 제외하고).
  • 6k + 3: 이는 3의 배수이므로 소수가 아닙니다(3을 제외하고).
  • 6k + 4: 이는 짝수이므로 소수가 아닙니다.
  • 6k + 1과 6k + 5: 소수가 될 가능성이 있습니다.

 

즉, 5와 7부터 시작해서 6씩 증가하면 6k +- 1형태의 숫자만 검사할 수 있다.

import sys
input = sys.stdin.readline

def Prime(num):
    if num <= 1:
        return 0
    if num <=3:
        return 1
    if num % 2 == 0 or num % 3 == 0:
        return 0
   
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return 0
        i += 6 #5, 11, 17, 23, 29 => 7, 13, 19, 25, 31
   
    return 1

n = int(input())

for _ in range(n):
    num = int(input())
    while not Prime(num):
        num += 1
    print(num)

 

<다른사람 풀이 참고>

대부분 소수판별 알고리즘으로 해결했다. 여기서 중요한건 제곱근을 활용해서 풀어야 한다는 점이다.

아래 처럼 함수에 단순히 2부터 제곱근까지의 숫자로 False와 True만 구분해준 후

메인 함수에서 n == 0, 1일 경우 2로 출력값을 고정하고 이후 2부터는 check함수에 집어 넣어서 반복문을 돌린다.

이런 것 보다 그냥 내가 작성한 코드가 조금 더 효율적인 것 같다.

import sys
input = sys.stdin.readline

N = int(input())

def check(x):
  for i in range(2, int(x**0.5)+1):
    if x % i == 0:
      return False
  return True

for i in range(N):
  n = int(input())  
  while True:
    if n==0 or n==1:
      print(2)
      break
    if check(n):
      print(n)
      break
    else:
      n+=1
728x90
반응형