백준 알고리즘
[Silver IV] 다음 소수 - 4134
성능 요약
메모리: 13152 KB, 시간: 164 ms
분류
브루트포스 알고리즘, 수학, 정수론, 소수 판정
문제 설명
정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.
출력
각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.
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
use std::io::{stdin, BufRead};
fn is_prime(x: i64) -> bool {
if x == 0 || x == 1 {
return false;
}
for i in 2..=(x as f64).sqrt() as i64 {
if x % i == 0 {
return false;
}
}
true
}
fn main() {
let stdin = stdin();
let mut reader = stdin.lock().lines().map(|line| line.unwrap());
let t: i32 = reader.next().unwrap().trim().parse().unwrap();
for _ in 0..t {
let z: i64 = reader.next().unwrap().trim().parse().unwrap();
let mut num = z;
loop {
if is_prime(num) {
println!("{}", num);
break;
} else {
num += 1;
}
}
}
}