개요알고리즘 풀이를 하다 보면 소수를 구할 때가 많습니다. 이때, 소수를 구하는 방식은 여러 가지가 있으며, 각각의 방식에 따라 시간 복잡도가 다르게 나타납니다. 가장 기본적인 방법은 O(N)의 시간 복잡도를 가진 소수 판별 함수를 사용하는 것입니다. 이 외에도 제곱근을 활용한 최적화 방법, 그리고 에라토스테네스의 체를 이용한 효율적인 소수 구하는 방법이 있습니다. 본 글에서는 이 세 가지 방법을 차례대로 살펴보겠습니다. 소수(Prime Number)란❓먼저 소수란 1과 자기 자신으로만 나누어 떨어지는 수로 "양의 약수를 두 개만 가지는 자연수"를 의미하며, 2, 3, 5, 7, 11 ... 등이 존재합니다. 기본 소수 판별 함수 (O(N))가장 간단한 방법은 주어진 숫자에 대해 1부터 그 숫자까지의 ..
소수
문제설명입력 & 출력나의 풀이import java.util.*;class Solution { public int solution(int[] nums) { int answer = 0; for(int i = 0 ; i 이번 문제는 배열의 요소 중 3개의 요소를 더해서 소수를 만드는 문제입니다. 브루트 포스 알고리즘을 사용하면 모든 가능한 조합을 시도하여 최적해를 놓치지 않기 때문에, 문제 해결의 확실성을 보장할 수 있습니다. 따라서 브루트 포스 알고리즘을 사용했습니다. 먼저 소수를 판별할 수 있는 isPrime()이라는 함수를 만들어줍니다. 해당 함수에서는 소수를 구하는 로직이 있습니다.소수(prime number)는 1과 자기 자신만을 약수로 가지는 자연수를 말합니다. 즉,..
