[백준 1929 파이썬/python] 소수 구하기

소수 구하기

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

1)

2)

소수 구하기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	233283	66564	46782	26.690%

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

풀이

1)

def get_prime_number(M, N):
    lst = []
    for i in range(M, N + 1):
        if i < 2:
            continue
        is_prime = True
        j = 2
        while j * j <= i:
            if i % j == 0:
                is_prime = False
                break
            j += 1
        if is_prime:
            lst.append(i)
    print('\n'.join(map(str, lst)))


M, N = map(int, input().split())
get_prime_number(M, N)

• 풀이과정
  1. def get_prime_number(M, N):: M과 N을 입력 인자로 받는 함수 get_prime_number를 정의합니다.
  2. lst = []: 소수를 저장할 빈 리스트 lst를 초기화합니다.
  3. for i in range(M, N + 1):: M부터 N까지의 숫자를 반복합니다.
  4. if i < 2:: i가 2보다 작은 경우,
  5. continue: 현재 반복을 건너뛰고 다음 숫자로 넘어갑니다. (0과 1은 소수가 아니므로)
  6. is_prime = True: i가 소수인지 아닌지를 저장할 변수 is_prime을 True로 초기화합니다.
  7. j = 2: 나눗셈에 사용할 j 값을 2로 초기화합니다.
  8. while j * j <= i:: j의 제곱이 i보다 작거나 같을 때까지 반복합니다. (i의 약수를 찾기 위한 조건)
  9. if i % j == 0:: i가 j로 나누어 떨어지면 (i가 j의 배수이면),
  10. is_prime = False: i가 소수가 아니므로, is_prime 값을 False로 변경합니다.
  11. break: 소수가 아닌 것이 확인되었으므로 while 루프를 종료합니다.
  12. j += 1: j 값을 1 증가시킵니다.
  13. if is_prime:: is_prime이 True인 경우 (i가 소수인 경우),
  14. lst.append(i): 소수인 i 값을 리스트 lst에 추가합니다.
  15. print('\n'.join(map(str, lst))): 리스트의 원소들을 문자열로 변환한 뒤, 각 원소를 개행 문자('\n')로 연결하여 한 줄에 하나씩 출력합니다.
  16. M, N = map(int, input().split()): 사용자로부터 두 정수 M과 N을 입력받습니다.
  17. get_prime_number(M, N): 입력받은 M과 N을 인자로 하여 get_prime_number 함수를 호출합니다.

2)

MAX = 1000000
check = [0]*(MAX+1)
check[0] = check[1] = True

for i in range(2, MAX+1):
    if not check[i]:
        j = i+i
        while j <= MAX:
            check[j] = True
            j += i
m, n = map(int,input().split())
for i in range(m, n+1):
    if check[i] == False:
        print(i)

• 풀이과정
  1. MAX = 1000000: 최대 범위를 1,000,000으로 설정합니다.
  2. check = [0]*(MAX+1): 최대 범위만큼의 길이를 가진 리스트를 생성하고, 모든 값을 0으로 초기화합니다. 이 리스트는 각 인덱스가 소수인지 아닌지를 확인하기 위해 사용됩니다. (0: 소수, 1: 소수가 아님)
  3. check[0] = check[1] = True: 0과 1은 소수가 아니므로, 해당 인덱스의 값을 True로 설정합니다.
  4. for i in range(2, MAX+1):: 2부터 최대 범위까지의 숫자를 반복합니다.
  5. if not check[i]:: 만약 현재의 i 값이 소수라면 (check[i]가 0이라면),
  6. j = i+i: j 값을 i의 2배로 설정합니다.
  7. while j <= MAX:: j 값이 최대 범위 이내인 동안 반복합니다.
  8. check[j] = True: j의 배수는 소수가 아니므로, 해당 인덱스의 값을 True로 설정합니다.
  9. j += i: j 값을 i만큼 증가시킵니다. 이렇게 하면 i의 배수를 확인할 수 있습니다.
  10. m, n = map(int,input().split()): 사용자로부터 두 정수 m과 n을 입력받습니다.
  11. for i in range(m, n+1):: 입력받은 m부터 n까지의 숫자를 반복합니다.
  12. if check[i] == False:: 만약 현재의 i 값이 소수라면 (check[i]가 0이라면),
  13. print(i): 소수인 i 값을 출력합니다.

  → 이 코드는 에라토스테네스의 체를 활용해 주어진 범위 내의 모든 소수를 출력하는 알고리즘을 구현!

Uploaded by N2T