728x90 반응형 소수2 [알고리즘/Python] 에라토스테네스의 체 에라토스테네스의 체 -> 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘. -> N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 소수란? 1과 자신 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 말한다. > 동작 과정 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.) 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다. > 장단점 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다. 그래서 다수의 소수를 찾아야 하는 문제에서 자주 사용된다. 하지만 알고리즘을 수행할 때 N의 .. 2023. 1. 18. [프로그래머스/Python][level 1] 소수 만들기 - 12977 [level 1] 소수 만들기 - 12977 문제 링크 성능 요약 메모리: 10.3 MB, 시간: 0.01 ms 구분 코딩테스트 연습 > Summer／Winter Coding（～2018） 채점결과 정확성: 100.0 합계: 100.0 / 100.0 문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다... 2023. 1. 13. 이전 1 다음 728x90 반응형
