[백준(BOJ)] 1978번 : 소수 찾기 - C++[CPP]

www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

---

 

⊙ 문제 접근 과정

 

소수 찾기니 제일 먼저 나머지 연산자를 생각했다.

나머지 연산자(%)를 이용해 for문을 돌리면 손쉽게 해결할 수 있다.

 

---

 

⊙ 문제 풀이

 

#include <iostream>

using namespace std;

int main() {
    int N;
    bool flag=true;
    int count=0;
    int count__=0;
    
    cin>>N; //입력받는 값의 개수

    int input[N]; //소수인지 판별하려는 값

    for (int i = 0; i < N; i++) {
        cin >> input[i];
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 2; j <= input[i]; j++) // begin 2 start
        {
            if(input[i]%j==0) { // 소수이면 count up 전 count__ up
                count__++;
                if(input[i]==j) {
                    if(count__==1) { // if count__, count= 1이면 소수 !
                        flag=false; // flag change
                        count__=0;
                    }else count__=0; // count__ reset
                }
                
            }
        }

        if(!flag) { //소수이니 count up and flag reset
            count++;
            flag=true;
        }
        
    }

    cout<<count; //count print


}

 

 

---

⊙ 결과

 

 

---

 

 

⊙ 마무리

 

 

시간 초과가 몇번 나왔다. 시간 복잡도에 대해 정확히 숙지하고 문제에 접근할 때,

시간 복잡도를 생각하며 알고리즘을 구현하도록 하자.