백준 1978번 : 소수 찾기 (C++,Python)

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

 

 

풀이

소수는 1과 자기 자신으로만 나누어 떨어지고 그 외의 수로는 나누어 떨어지지 않는 수이다. (단, 1은 소수가 아니다.)

 

따라서 1과 자기자신의 사이의 수(1과 자기 자신은 제외)들로 모두 나누어보면 소수인지 확인할 수 있다!

1이 소수가 아닌 것에 유의하면서 구현해 보자.

(역으로 생각하여 전체에서 소수가 아닌 것의 개수를 빼면 간편하게 구현할 수 있다. 물론 소수인 것의 개수를 세도 좋습니다.)

 

C++ 정답코드

#include <bits/stdc++.h>

using namespace std;

int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

   

    int n;

    cin >> n;

    int res = n;

    for(int i = 0; i<n; i++)

    {

        int x;

        cin >> x;

        if(x == 1)

        {

            res--;

            continue;

        }

       

        for(int j = 2; j<x; j++)

        {

            if(x%j == 0)

            {

                res--;

                break;

            }

        }

    }

    cout << res << endl;

    return 0;

}

 

Python 정답코드

n = int(input())

arr = map(int,input().split())

res = n

for x in arr:

    if(x == 1):

        res-=1

        continue

    for i in range(2,x):

        if(x%i == 0):

            res-=1

            break

print(res)

 

생각해 보면 좋은 것

위 코드의 연산량은 어떻게 될까?

- N번의 소수 판정을 해야 하고 한 번의 소수 판정에 최대 1000번(주어지는 값의 최댓값)의 루프를 돈다. 최악의 경우 N*1000 = 약 100,000번의 연산이 이루어진다.

 

ps에서는 보통 컴퓨터가 1초에 1억 번 연산이 가능하다고 잡는데 이를 감안하면 여유롭게 통과하는 연산이다.

이를 Big-O표기법으로 쓰면 O(N * max(A)) (A는 주어진 수들의 리스트)라 할 수 있다.

 

만약 N의 제한이 크거나 주어진 수의 최댓값이 크다면 어떻게 풀어야 할까?