[백준 알고리즘] 1929번 : 소수 구하기, c++

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

1929번: 소수 구하기

c++로 백준 1929번 문제를 풀어보겠다.

 

 

 

 

 

 

문제

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

입력

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

출력

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

예제 입력 1 복사

3 16

예제 출력 1 복사

3
5
7
11
13

 

 

 

 

 <문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

이렇게 코드를 작성했을 때 visual studio에서는 잘 돌아갔지만 백준 알고리즘 사이트에서는 '시간초과'가 떴다.

 

 

따라서 이러한 오류를 해결한 코드는 다음과 같다.

1. 알고리즘의 복잡도를 고려해 for문 안에 또 for문이 있는 형태인 중첩for문 형태를 없애기 위해 새로운 함수를 정의했다.

2. 그 함수안에는

    if(i<2)
        return false; 

위의 코드와 같이 2보다 작을 때 바로 원함수로 돌려보내도록 했고,

3. j<=i/2형태가 아닌 j*j<=i 형태로 for문의 조건을 바꿔주었다.

 

 

- 최종적으로 작성한 코드 설명 -

1. int 형의 M, N을 선언한 후 입력받는다.

2. M부터 N까지 돌며 숫자가 소수라면 출력하고 소수가 아니라면 그냥 지나가도록 한다.