소수의 개수
-
JUNGOL 실력키우기 수학2 - 소수와 합성수 | 소수 | 소수 구하기 | 소수의 개수보관함 2020. 2. 5. 23:33
기초 다지기에서 배운 내용을 응용하여 문제를 해결해야 하는 실력 키우기입니다. 실력 키우기는 비슷한 문제 유형별로 묶어서 풀어보겠습니다. 이번 포스팅에서는 수학2의 소수 시리즈를 풀어보겠습니다. 2811 : 소수와 합성수 이 문제는 단순하게 2부터 입력된 숫자까지를 돌면서 나눠지는 값이 있는지를 확인하여 나눠지는 경우 소수로 판단할 수도 있으나 조금 더 생각하면 범위를 줄일 수 있다는 것을 알 수 있습니다. 숫자를 나눌 수 있는 가장 큰 값은 해당 숫자의 루트 값 까지라는 것입니다. 즉, 2부터 해당 숫자까지를 나누는 게 아니라 해당 숫자의 루트까지만 나눠서 확인하면 되는 것입니다. 그렇게 하면 최대로 나누는 횟수는 10억 회가 아니라 10억의 루트 값인 31,622 회가 됩니다. #include #in..