백준 1929번 소수 구하기

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

1929번: 소수 구하기

 

문제

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

 

입력

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

 

출력

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

 

Python 코드

import math
n, m = map(int, input().split())

for i in range(n, m+1):
    if i==1:
        continue
    for j in range(2,int(math.sqrt(i)+1)):
        if (i%j) == 0:
            break
    else:
        print(i)

소수를 구하는 문제 중 가장 기본적인 문제이지만 처음 풀때 시간초과만 10번은 띄운것같다

 

에라토스테네스의 체를 익히면 간단히 풀 수 있는 문제이기에 아무것도 상태에서 계속 시도하기보다는 알고리즘의 개념부터 익힌 다음 풀어보기를 추천한다.

 

소수 구하기

이번에는 문제 자체가 소수를 구하는 것이므로 소수를 구하는 알고리즘을 설명하겠다

 

1. 2이상의 임의의 수 x가 소수인지 확인하기 위하여 보통 2부터 x까지  모든 수로 나누어보며 확인한다.

def is_prime(x):
	for i in range(2, x):
    	if x % i == 0:
        	return Fasle		#소수 아님
	return True			#소수임

이 방식은 위 문제를 시간 초과로 풀지 못하기에 더 빠른 방식이 필요하다

 

먼저 16이 소수인지 판별하는 과정을 예로 들어 두번째 방법을 설명하겠다.

16의 약수는 다음과 같다.

• 1 * 16
• 2 * 8
• 4 * 4
• 8 * 2
• 16 * 1

16의 제곱근끼리의 곱  4 * 4 이후로는 이전의 인수와 동일한 수가 반복되는걸 알 수 있다.

4번째 줄 8 * 2는 2 * 8의 순서만 반대로 정렬한 것과 같다.

 

2. 2 이상의 정수 x를 소수인지 판별하기 위하여 그 수의 제곱근까지만 확인하면 된다.

def is_prime_2(x):
	for i in range(2, int(x**2+1)):
    	if x % i ==0:
        	return False		#소수가 아님
	return True			#소수임

 

마지막으로 에라토스테네스의 체는 대표적인 소수 판별 알고리즘이며 과정은 다음과 같다.

1. 2 부터 x까지 모든 자연수를 나열
2. 가장 작은 소수i를 탐색
3. 남은 수 중 i의 배수를 모두 제거(i는 제거하지 않음)
4. 2~3의 과정을 i가 sqrt(x)가 될때까지 반복

3. 에라토스테네스의 체

def is_prime_3(x):
	num_list=[True * for _ in range(x+1)]		#처음에 리스트를 소수로 초기화
    num_list[0]=False
    num_list[1]=False			#0과 1을 제외

	for i in range(2, int(x**2+1)):		#2부터 x의 제곱근까지 확인
    	if num_list[i] == True:		#i가 소수일때
        	temp=2
            if temp * i < x:		#i의 모든 배수 제외
            	num_list[temp] = False	
                temp += 1

소수를 구하는 대다수의 문제는 에라토스테네스의 체를 사용하여 풀 수 있다.