코딩 테스트 준비 1단계 기본기 - 백준 1978

 

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

코딩테스트 대비를 위한 백준 문제 추천

Part 1 준비운동 - 소수 찾기 (백준 1978)

문제 출처: https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

풀이

초보자 입장에서 풀고 한 단계 더 나아가 소수찾기 알고리즘 원픽 에라토스테네스의 체를 이용하여 풀어보았습니다.

결과적으로 30행에서 반복문의 arr[j]는 모두 소수가 아니기 때문에 이를 체크 해줌으로써 쉽게 소수를 걸러낼 수 있습니다.

에라토스테네스의 체에 대한 개념은 아래 링크를 통해 학습할 수 있습니다.

https://jow1025.tistory.com/12

 

코드

#include<iostream>
using namespace std;
int arr[1001];
int main()
{
    int t, i, num, cnt = 0;
    cin >> t;
    while (t--)
    {
        cin >> num;
            //솔루션1: 입력범위가 작으면 이대로 풀자.
        /*if (num > 1) {
            for (i = 2; i < num; i++)
            {
                if (num % i == 0)
                    break;
            }
            if (i == num)cnt++;
        }*/
 
        //솔루션 2: 입력범위가 크다싶으면 그냥 에라토스테네스의체 쓰자.
 
        //0과 1은 소수가 아니므로 1값으로 체크
        arr[0] = 1, arr[1] = 1;
        for (int i = 2; i < 1001; i++)
        {
            for (int j = i * i; j < 1001; j += i)
            {
                //소수가 아닌 경우 체크
                 arr[j] = 1;
            }
        }
        if (arr[num] == 0)cnt++;
    }
    cout << cnt << endl;
    return 0;
}

 

결과