백준 소수구하기1 백준 1929 소수 구하기 시간초과가 뜨지 않게 소수를 구하려면 에라토스테네스의 체 방법이 필요하다. 소수는 1과 자기자신만을 약수로 가지는 수이다. for문을 돌리면서, 2부터 해당값까지 배수인 숫자들을 모두 true로 반환한다. 여기서 해당값이 𝑝 곱하기 𝑞라면 결과적으로 𝑝 와 𝑞 중 하나는 반드시 √N 보다 작거나 같다. 즉, √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미이므로 소수가 아니게 되는 것이다. import java.util.Scanner; public class Main { public static boolean[] prime; public static void main(String[] args) { // TODO Auto-generated .. 2022. 8. 2. 이전 1 다음