[BOJ] 1929. 소수 구하기 (C,Python3)

• 코딩 초보. 구현을 목표로 하였기에 비효율적일 수 있습니다.

---

1929. 소수 구하기 

 

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

 

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

 

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

 

 

---

1.Python

 

m,n=map(int,input().split())
prime=[]

#prime list
for i in range(m,n+1):
    prime.append(i)
    
for i in range(2,n+1):
    for j in range(2,n+1):
        s=i*j
        if s>n+1:
            break
        if s in prime:
            prime.remove(s)
#print 
for i in range(len(prime)):
    print("%d" %(prime[i]))

처음에 시간초과가 뜬 코드이다. 일일히 소수가 맞는지를 판별하도록 했는데, 이러면 시간초과가 떴다. 해결방법을 위해서 에라토스테네스의 체를 활용했다.

 

에라토스테네스의 체란, 다수의 자연수에서 소수를 판별할 때 주로 사용하는 알고리즘이다. 수업시간에 배웠듯, 가장 작은 소수로 2를 선택하고 2의 배수를 지워나가고, 그 다음으로 3을 선택해서 3의 배수를 제거해나가는 알고리즘이다. 위 코드도 비슷하게 활용했지만 시간초과가 뜬 이유가 2부터 n까지 모두 검토했기 때문이라고 생각된다. 그래서 이번에는 함수와 제곱근을 이용하여 코드를 새로 짰다. 

 

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

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

for i in range(m,n+1):
    if prime(i)==True:
        print(i)

---

2.C99

 

#include <stdio.h>
#include <math.h>

int prime(int num) {
	if (num == 1) {
		return -1;
	}
	else {
		for (int i = 2; i < (int)sqrt(num) + 1; i ++) {
			if (num % i == 0) return -1; 
		}
		return 1; 
	}
}
main() {
	int m, n;
	scanf("%d %d", &m, &n);

	for (int i = m; i <= n; i++) {
		if (prime(i) == 1) {
			printf("%d\n", i);
		}
	}


}

C언어로도 비슷하게 구현할 수 있다.