c c++ 언어 공부

백준 4134번 : 다음 소수 (C언어)

Code C 2023. 3. 21. 22:07

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

 

4134번: 다음 소수

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

www.acmicpc.net

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
 
int check(long long value)
{
    long long i;
    int score = 0;
    for (i = 2; i * i <= value;i++)
    {
        if ((value % i) == 0)
        {
            score = 1;
            break;
        }
    }
    return score;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    long long i = 0;
    long long value = 0;
    while (n--)
    {
        scanf("%lld", &value);
        if (value == 0 || value == 1)
        {
            printf("%d\n",2);
            continue;
        }
        for (i = value; i < 5000000000; i++)
        {
            int a = check(i);
            if (a == 0)
            {
                printf("%lld\n", i);
                break;
            }
        }
    }
}
 cs

문제풀이 : 

소수를 구할 때 값의 제곱근만큼만 체크를 하면 소수인지 아닌지 알 수 있다. ex) 11을 확인할 때  4의 제곱은 16, 3의 제곱은 9 이므로 3까지 나누었을 때 나머지가 있으면 소수이다.