백준, C++) 1978, 2581, 5086

1978

 

 

#include <iostream>

#include <vector>

using namespace std;

int main()

{

    int x;

    int count = 0;

    vector<int> factors;

    cin >> x;

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

    {

        int num = 0;

        cin >> num;

        factors.push_back(num);

    }

    for (int i = 0; i < factors.size(); i++)

    {

        bool isPrimeNum = false;

        if (factors[i] == 2)

        {

            count++;

            continue;

        }

        else

        {

            for (int j = 2; j < factors[i]; j++)

            {

                if(factors[i]%j==0)

                    {

                        isPrimeNum = false;

                        break;

                    }

                else

                    isPrimeNum = true;

            }

        }

        if(isPrimeNum) count++;

    }

    cout << count;

    return 0;

}

 

본인이 짠 코드

-> 비교적 길고, 공간복잡도 + 시간복잡도가 큼

 

에라토스테네스의 체란?

 

 

"에라토스테네스의 체" 방식을 사용한 코드

->

#include <iostream>

#include <vector>

using namespace std;

// 소수를 판별하는 에라토스테네스의 체 함수

vector<bool> sieve(int max) {

    vector<bool> isPrime(max + 1, true);

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= max; i++) {

        if (isPrime[i]) {

            for (int j = i * i; j <= max; j += i) {

                isPrime[j] = false;

            }

        }

    }

    return isPrime;

}

int main() {

    int n;

    cin >> n;

    vector<int> numbers(n);

    int maxValue = 0;

    // 숫자 입력받고 최대값 구하기

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

        cin >> numbers[i];

        if (numbers[i] > maxValue)

            maxValue = numbers[i];

    }

    // 최대값까지의 소수 여부를 미리 계산

    vector<bool> isPrime = sieve(maxValue);

    // 소수 개수 세기

    int count = 0;

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

        if (isPrime[numbers[i]])

            count++;

    }

    cout << count << endl;

    return 0;

}

->

공간 복잡도도 줄였고, 시간 복잡도도 O(1)

 

---

2581

 

위 방식을 조금 이용한 2581

 

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

    int x = 0, y = 0;

    int res = 0;

    cin >> x;

    cin >> y;

    vector<int> PrimeNum;

    for (int start = x; start < y + 1; start++)

    {

        if (start < 2) continue;

        bool isPrimeNum = true;

        for (int i = 2; i * i <= start; i++)

        {

            if (start % i == 0)

            {

                isPrimeNum = false;

                break;

            }

        }

        if (isPrimeNum)

            PrimeNum.push_back(start);

    }

    if(!PrimeNum.empty())

    {

        for (int val : PrimeNum)

            res += val;

        cout << res << "\n";

        int min = *min_element(PrimeNum.begin(), PrimeNum.end());

        cout << min << "\n";

    }

    else    cout << -1;

    return 0;

}

 

<algorithm>  -> *min_element(); 사용

 

min_element()는 최솟값을 가리키는 반복자 -> *를 붙여서 주소 안의 값을 알아야 함.

 

 

 

---

5086

소인수 분해는 같은 걸 반복 -> 재귀를 생각 (반복문으로도 가능)

 

#include <iostream>

#include <vector>

using namespace std;

void primeFactorization(int x, vector<int>& factors) {

    if (x == 1) return;

    for (int i = 2; i <= x; i++) {

        if (x % i == 0) {

            factors.push_back(i);

            primeFactorization(x / i, factors);

            return;

        }

    }

}

int main() {

    int x;

    cin >> x;

    vector<int> factors;

    primeFactorization(x, factors);

    for (int val : factors)

        cout << val << '\n';

    return 0;

}