소수 찾기 프로그램 방법 n-1까지 구하기 O(n) n-1 까지 소수를 모두 구하는 다이나믹 프로그래밍으로 알고리즘 짜기 소수 배열을 만들어서 소수 배열만 돌면서 나누어지는지 판단 O(n) 소수 배열을 만드는 데에 O(n) => 메리트 없음 루트 n까지 돌리면서 짝수 제외하기 O(sqrt(n)) 조건 추가 몇 개의 소수( 3, 5 )를 가지고 해당 수의 배수이면 뛰어넘기 3, 5 계산 시 나누어떨어지지 않았으면 해당 수의 배수에도 나누어떨어지지 않음 구현 시 주의 해당 수가 3으로 나누어떨어지는지, 5로 나누어떨어지는지를 계산하려면 모듈러 연산을 사용해야하는데 시간이 오래 걸림 변수 하나씩 지정하고 1씩 더하는 방법으로 구성 3과 5의 공배수가 나오면 먼저 거치는 3의 if문에서 continue 됨으로 ..