백준알고리즘 1929 소수구하기 [C++]

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

1929번: 소수 구하기

---

정답코드

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int m, n, pnum;
    vector<int> v;

    cin >> m >> n;

    for(int i = m; i <= n; i++){
        pnum = sqrt(i);
        if(i == 2 || i == 3){
            v.push_back(i);
            continue;
        }
        if((i % 2) == 1){// 홀수이면
            for(int j = 2; j <= pnum; j++){
                if(i % j == 0) break;
                if(j == pnum) v.push_back(i);
            }
        }
    }

    for(int i = 0; i < v.size(); i++){
        cout << v[i] << '\n';
    }

}

---

풀이과정

bool primeNum(int num){ // 시간초과
    if(num % 2 == 0) return false;
    for(int i = 3; i < num; i++){
        if(num % i == 0) 
            return false;
        if(i > num/2) 
            return true;
    }
}

PrimeNum을 판별하는 함수를 사용했으나 시간초과로 인해 제출하지 못했다.

소수를 판별하는 절차를 외워두면 편하게 풀 수 있을듯하다.

 

1. 2나 3이라면 소수이다.

2. 2부터 sqrt(num)까지 나누었을 때 나누어 떨어지면 소수가 아니다.