목록소수찾기 (1)

문홍의 공부장

[Java] 프로그래머스 Lv.1 소수 찾기 풀이 : 에라토스테네스의 체(소수 구하기 알고리즘)

소수 구하기 문제라고 가볍게 생각했다가, 효율성 테스트에서 시간초과를 맞고 띠용해서 찾으며 공부한 소수 구하는 알고리즘. 에라토스테네스의 체라는 알고리즘을 이번에 처음 접했다. 이름만 들어도 고대 그리스 수학자 느낌이 물씬 느껴진다.. 문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 1000000이하의 자연수입니다. 풀이 1. 자기 자신보다 작은 수로 나누어본다. 나누어 떨어지면 소수가 아니다. 가장 기본적인 방법. 입력받은 수 n 까지 반복문을 돌리며 소수를 찾아 flag 값을 바꾼다. 자기 자신(i)보다 작은 수(j)로 나누어 하나..
알고리즘/프로그래머스 2020. 2. 8. 00:40
이전 Prev 1 Next 다음