[백준] 4134 다음 소수 (C++)

 

입출력

 

 

 

 

 

 

---

풀이

 

 

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

bool find(long long num)
{
    for (long long j = 2; j <= sqrt(num); j++)
    {
        if ((num) % j == 0)
			return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    long cnt;
    cin >> cnt;

    long long n;
    vector<long long> ns;
    for (long long i = 0; i < cnt; i++)
    {
        cin >> n;
        ns.push_back(n);
    }
    

    for (long long i = 0; i < ns.size(); i++)
    {
        if(ns[i] == 0 || ns[i] == 1)
        {
            cout << "2" << "\n";
        }
        else
        {
            while (find(ns[i]))
            {
                ns[i]++;
            }
            cout << ns[i] << "\n";
        }
    }
    return 0;
}

 

입력 받은 수부터 하나씩 올려가면서 해당 수가 소수인지 아닌지 ( 자기 자신보다 작은 수에서 나누어떨어지는지 아닌지) 확인한다

소수인지 아닌지 확인하는 과정에서 해당 수의 제곱근보다 작은 수들만 나누어지는지 확인하면 시간 단축을 할 수 있다