[BOJ][C++] 백준 4134번: 다음 소수 (Silver IV)

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

문제

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

 

풀이

아르토스테네스의 체가 무력화되는 문제

소수의 정의를 이용해야한다.

말 그대로 처음부터 자기 자신까지 모든 수로 다 나눠보고 하나라도 나누어 떨어지면 소수가 아닌걸로 소수 여부 판단하기

 

이때 시간초과가 안나기 위해서는 전부 도는 대신 반절만 루프를 해야한다

예를들어 8이 소수인지 판단할때는 1,2,4,8 중에서 2까지만 나눠보면 된다.

24를 판단할때는 1,2,3,4,6,8,12,24 중 4까지만

100을 판단할때는 1,2,4,5,10,20,25,50,100 중 10까지만

연산해보면 되기 때문에 반복문을 j*j<=i 까지만 돌려야한다.

 

25%정도에서 틀렸습니다가 뜬다면 오버플로우를 의심해보자

최대값인 4000000000 을 넣었을 때 4000000007이 나와야한다.

코드에서 쓰이는 대부분 변수의 자료형은 int가 아닌 Long long 이다. 

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

bool isPrime(ll i) {
    if(i==0 || i==1) {
        return false;
    }
    
    for(ll j=2; j*j<=i; j++) {
        if(i%j==0) {
            return false;
        }
    }
    return true;
}

ll solution(ll n) {
    for(ll i=n; true; i++) {
        if(isPrime(i)) {
            return i;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int t;
	ll n;
	cin >> t;
	while(t--) {
	    cin >> n;
	    ll ans = solution(n);
	    cout << ans << "\n";
	}
	
    return 0;
}