백준-약수, 배수와 소수 1978 소수 찾기

소수 찾기

N이하의 소수를 모두 찾기

베이직 기법으로 찾아본 후 시간을 단축할 수 있는 방법을 고려해본다.

자세한것은 다음 글을 확인해 보면 좋을 것 같다.

https://cyphen156.tistory.com/144

알고리듬#2 소수판정법(primarity Test)

제약사항

• 0 < Input <= 100
• 0 < Number <= 1,000

주의 사항

없다.

CPP풀이

소수 찾기_1978_Basic.cpp

/**
 * 백준 소수 찾기_1978_Basic
 * N이하의 소수를 모두 찾기
 * 베이직 기법으로 찾아본 후 시간을 단축할 수 있는 방법을 고려해본다.
 * 
 * 제한사항
 *****************************************
 * 0 < Input <= 100                      *
 * 0 < Number <= 1,000                   *
 *****************************************
 *
 *
 *
 * 주의
 * 없다.
 * 
 * 풀이시간 10분
 */


#include <iostream>

using namespace std;

int main(void)
{
    int N;
    cin >> N;

    int checkPrimal[1001] = { 1, 1, 0 };
    int cnt = 0;
    // 0과 1은 소수가 아니다.
    for (int i = 2; i < 1001; ++i)
    {
        for (int j = 2; j < i; ++j)
        {
            if ((i % j) == 0)
            {
                // 소수가 아니다
                checkPrimal[i] = 1;
            }
        }
    }
    for (int i = 0; i < N; ++i)
    {
        int input;
        cin >> input;
        if (checkPrimal[input] == 0)
        {
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

 다음은 에라토스테네스의 체를 이용한 방식이다.

소수 찾기_1978_ Sieve of Eratosthenes.cpp

/**
 * 백준 소수 찾기_1978_Sieve of Eratosthenes
 * N이하의 소수를 모두 찾기
 * 에라토스테네스의 체로 소수인지 판볋한다.
 * 
 * 제한사항
 *****************************************
 * 0 < Input <= 100                      *
 * 0 < Number <= 1,000                   *
 *****************************************
 *
 *
 *
 * 주의
 * 없다.
 * 
 * 풀이시간 10분
 */


#include <iostream>
#include <cmath>

#define SIZE 1001

using namespace std;

int main(void)
{
    int N;
    cin >> N;

    // true is not Prime
    // default == false means Prime
    bool checkPrimal[SIZE] = {false};

    checkPrimal[0] = checkPrimal[1] = true;

    int cnt = 0;

    // 선제적 소수 판정
    for (int i = 2; i * i < 1001; ++i)
    {
        if (!checkPrimal[i])
        {
            for (int j = i*i; j < SIZE; j += i)
            {
                checkPrimal[j] = true;
            }
        }
    }

    for (int i = 0; i < N; ++i)
    {
        int input;

        cin  >> input;
        if (!checkPrimal[input])
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리 에 있습니다.

Workspace/알고리듬 풀이 at main · cyphen156/Workspace · GitHub

Workspace/알고리듬 풀이 at main · cyphen156/Workspace