[백준 알고리즘] 백준 1929번 소수 구하기 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 1929번 소수 구하기 파이썬(Python)

1) 문제번호 : 1929번

 

2) 문제 출처

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

2. 문제

부산일과학고등학교의 효진이는 수학의 귀재이다. 어떤 문제라도 보면 1분 내에 풀어버린다는 학교의 전설이 내려올 정도였는데, 이런 킹ㅡ갓 효진에게도 고민이 생겼다. 대부분의 문제에서 반복되는 연산이 있었기 때문이다! 이 연산은 너무 길어서 종이에 풀던 효진이는 너무 고통스러워서, 자신이 새로 연산자를 만들기로 했다.

연산자의 기호는 ＠으로, A＠B = (A+B)×(A-B)으로 정의내리기로 했다.

하지만, 효진이는 막상 큰 숫자가 들어오자 계산하기 너무 귀찮아졌다.

효진이를 도와 정수 A, B가 주어지면 A＠B를 계산하는 프로그램을 만들어주자!

 

3. 제약사항

4. 입력

첫째 줄에 A, B가 주어진다. (1 ≤ A, B ≤ 100,000)

 

5. 출력

 첫째 줄에 A＠B의 결과를 출력한다.

 

6. 풀이

- 소수는 1부터 그 소수까지를 확인하는게 아닌 제곱근까지만 확인하면 된다.

- 그래서, isPrime 함수를 만들어 2부터 sq까지 소수를 판별한다.

7. 소스 코드

import math
import sys
input = sys.stdin.readline

def isPrime(num) :
    #만약 1이라면 소수가 아니므로 false
    if num==1: return False

    #제곱근까지만 확인
    sq = int(math.sqrt(num))

    for i in range(2, sq+1):
        #나눠지면 소수가 아님
        if num % i == 0 : return False

    return True

#자연수 M과 N 입력
M, N = map(int, input().split())

#M부터 N까지 소수면 소수 출력
for i in range(M, N+1):
    if isPrime(i) :
        print(i)

---