1 분 소요

1929번: 소수 구하기

문제

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

입력 조건

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다.

(1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력 조건

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


첫 번째 시도 .

 #include <iostream>
 #include <cmath>
 using namespace std;
 
 int main(){
     int m, n;
     cin >> m >> n;
     
     bool isPrime = true;
     for(int x = m; x <= n; x++){
         isPrime = true;
         if(x == 1){continue;}
         else if(x == 2){
             cout << 2 << endl;
             continue;
         }
         double checkNum = pow( x, 0.5) + 1;
         for (int i = 0; i < checkNum;  i++){
             if(x % i == 0){
                 isPrime = false;
                 break;
             }
         }
         if (isPrime){
             cout << x << "\n";
         }
     }
 }

»intput

3 16

»output

 3
 5
 7
 11
 13

success

image-20220829175103248

🌝 Thinking

double checkNum = pow( x, 0.5) + 1;
for (int i = 0; i < checkNum;  i++){}

이 부분에서 checkNum이라는 변수를 따로 만들지 않으면

for 구문이 순회할 때마다, cmath라이브러리에서 pow함수를 불러와야 하여 시간 초과를 야기할 수 있다.

따라서 CheckNum변수를 만들어 함수의 호출횟수를 줄여주었다.

( 파이썬에서는 **0.5 연산을 통하여 for구문에서 바로 선언을 하였지만 Cpp에서는 제곱근을 함수를 호출하여, 처리를 해주어야 한다. 따라서 함수를 호출에 반복문안에 포함되지 않도록 신경을 써주면 시간 초과문제를 피할 수 있었다.)

💡 깨달은 점.

소수찾기에서 숫자를 조사하는 과정에서 N = 1과 2는 예외사항으로 두어야한다는 점을 명심하자.

댓글남기기

참고