소수 구하기

1987번 문제 : 소수 찾기

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

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int num;
    cin >> num;
    int counter = 0;
    vector<int> v;
 
    while (num > 0)
    {
        int inp;
        cin >> inp;
        v.push_back(inp);
        num--;
    }
 
    for (auto i:v)
    {
        if (i != 1)
        {
            int j = i - 1;
            while (true)
            {
                if (i % j != 0) {
                    j--;
                }
                else {
                    if (j == 1)
                        counter++;
                    break;
                }
            }
        }
    }
 
    cout << counter;
 
    return 0;
}

2581번 문제 : 소수

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

#include <iostream>
#include <vector>
using namespace std;
 
void FindPrimeNumber(int n, vector<int>& v)
{
    if (n != 1)
    {
        int j = n - 1;
        while (true)
        {
            if (n % j != 0) {
                j--;
            }
            else {
                if (j == 1) 
                    v.push_back(n);
                break;
            }
        }
    }
}
 
int main() {
    int a, b;
    cin >> a >> b;
    vector<int> v;
 
    for (int i = a; i <= b; i++)
    {
        FindPrimeNumber(i, v);
    }
 
    if (!v.empty()) 
    {
        int sum = 0;
        int min = v.front();
        for (auto i : v)
        {
            sum += i;
            if (i < min)
                min = i;
        }
    
        cout << sum << endl << min;
    }
    else
        cout << "-1";
 
    return 0;
}

1929번 문제 : 소수 구하기

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

#include <iostream>
#include <vector>
using namespace std;
 
void CheckPrimeNumber(int n, int s, vector<int>& v)
{
    //Count Prime Number using SieveOfEratosthenes
    bool *prime = new bool[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p*p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p = s; p <= n; p++)
    {
        if (prime[p] == true)
            v.push_back(p);
    }
 
    delete[] prime;
}
 
int main() {
 
    int start, end;
    cin >> start >> end;
    vector<int> v;
 
    CheckPrimeNumber(end, start, v);
 
    for (auto i : v)
        cout << i << "\n";
 
    return 0;
}

메모:

-에라토스테네스의 체 활용, 시간 복잡도: O(n*log(log(n)))

참고사이트: https://www.geeksforgeeks.org/sieve-of-eratosthenes/

4948번 문제 : 베르트랑 공준

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

#include <iostream>
#include <vector>
using namespace std;
 
void CheckPrimeNumber(int n, int s, vector<int>& v)
{
    //Count Prime Number using SieveOfEratosthenes
    bool *prime = new bool[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p*p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p = s; p <= n; p++)
    {
        if (prime[p] == true)
            v.push_back(p);
    }
 
    delete[] prime;
}
 
int main() {
 
    vector<int> answer;
 
    while (true)
    {
        vector<int> v;
        int input;
        cin >> input;
        
        if (input != 0)
        {
            if (input != 1)
            {
                CheckPrimeNumber(input * 2 - 1, input + 1, v);
                answer.push_back(v.size());
            }
            else
            {
                answer.push_back(1);
            }
            
        }
        else
            break;
    }
 
    for (auto i : answer)
        cout << i << endl;
 
    return 0;
}

9020번 문제 : 골드바흐의 추측

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
void CheckPrimeNumber(int n, vector<int>& v)
{
    //Count Prime Number using SieveOfEratosthenes
    bool *prime = new bool[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        prime[i] = true;
    }
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p*p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p = 2; p <= n; p++)
    {
        if (prime[p] == true)
            v.push_back(p);
    }
 
    delete[] prime;
}
 
int main() {
 
    vector<int> answer;
    int num;
    cin >> num;
 
    for (int i = 0; i < num; i++)
    {
        vector<int> v;
        int input;
        cin >> input;
        CheckPrimeNumber(input, v);
        int temp = input / 2;
 
        while (temp > 1)
        {
            if (find(v.begin(), v.end(), temp) != v.end())
            {
                if (find(v.begin(), v.end(), input - temp) != v.end())
                {
                    answer.push_back(temp);
                    answer.push_back(input - temp);
                    break;
                }
            }
 
            temp--;
        }
    }
 
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer.at(i) << " ";
        if (i % 2 == 1)
            cout << endl;
    }
 
 
    return 0;
}