[Cpp]소수 구하기

🤔소수 구하기

소수(Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다.

🔑반복문으로 구현

#include <iostream>

int main()
{
    int count, num;

    std::cin >> num;

    // 입력받은 num까지의 소수 구하기
    for(int i = 2; i <= num; ++i)
    {
        count = 0;

        for(int j = 2; j <= i; ++j)
        {
            // i가 j로 나눠지면 count 1 증가. count가 2이상이면 소수가 아님
            if(i % j == 0)
            {
                ++count;
            }
        }

        //  count가 1이면 i는 자기 자신으로만 나눠진다는 뜻이므로 해당 i는 소수
        if(count == 1)
        {
            std::cout << i << " ";
        }
    }
}

🔑재귀함수로 구현

#include <iostream>

int GetPrime(int a, int b)
{
    int result = 0;

    if(b <= 0)
    {
        return 0;
    }

    if(a % b == 0)
    {
        result =  1;
    }
    else
    {
        result =  0;
    }

    result += GetPrime(a, b -1);

    return result;
}

int main()
{
    int count, num;

    std::cin >> num;

    for(int i = 0; i < num; ++i)
    {
        count = GetPrime(i, i);

        if(count == 2)
        {
            std::cout << i << " ";
        }
    }
}

🔑에라토스테네스의 체

#include <iostream>
#include <cmath>

int main()
{
    int num;
    int count = 0;

    std::cout << "Enter a number: ";
    std::cin >> num;

    int* arr = new int[num + 1];

    for (int i = 2; i <= num; ++i)
    {
        arr[i] = i;
    }

    for (int i = 2; i <= std::sqrt(num); ++i)
    {
        if (arr[i] == 0)
        {
            continue;
        }

        for (int j = 2 * i; j <= num; j += i)
        {
            arr[j] = 0;
        }
    }

    for (int i = 2; i <= num; ++i)
    {
        if (arr[i] != 0)
        {
            std::cout << arr[i] << " ";
        }
    }

    delete[] arr;
    arr = nullptr;
}