7. python 기본 수학2 - 백준 1978, 백준 1929

---

 

 

백준 1978

소수 찾기

문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력
첫 줄에 수의 개수 N이 주어진다. N은 100 이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력
주어진 수들 중 소수의 개수를 출력한다.

#백준 1978

N = int(input())    #입력받을 개수입력

count = 0 #소수가 있을 때마다 +1

number = map(int, input().split()) #입력받을 숫자입력 

for num in number:         
    if num > 1 :          
        for j in range(2, num): #for else 문을 사용
            if num % j == 0:    # 나눈 나머지가 0이면 소수가 아님
                break
        else:
            count += 1 #나눈 나머지가 0이아니면 소수임
                #소수일때마다 +1

print(count)

 

 

 

백준 1929

소수 구하기

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

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

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

#백준 1929

#에라토스테네스의 체 사용하지 않으면 타임아웃 발생하기 때문에
#'에라토스테네스의 체' 사용
#에라토스테네스의 체는 가장 대표적인 소수 판별 알고리즘
#에라토스테네스의 체는 특정한 숫자의 제곱근까지만 약수의 여부를 검증하는 방식
#일반적인 소수 판별 알고리즘의 시간복잡도인 O(N)에서 O(N**0.5)로 줄게되어 시간이 단축된다.

M, N = map(int, input().split())
if M < 2:   #M이 1일 때를 생각해 줘야 하기때문에 2보다 작으면 M=2라고 해둠
    M = 2

for i in range(M, N+1): 
    for j in range(2, int(i**0.5)+1): #여기서 에라토스테네스의 체 사용 (i**0.5)
        if i%j ==0:	#나머지가 없기때문에 소수가 아님
            break	#더이상 검사할 필요 없으므로 멈춤
    else:
        print(i)

 

 

 

 

​

위에 글 내용은 오류 사항이 존재할 수 있습니다!

수정 사항이 있을 시 알려주시면 감사하겠습니다.