백준_1418

• 1418 - 문제
• 문제풀이

1418 - 문제

문제풀이

• K-세준수 (어떤 자연수의 소인수중 최댓값이 K보다 크지 않을때 그 수) 의 개수를 구하는 문제
• 처음에는 2 ~ N 까지 돌아가면서 해당 수의 소인수들의 리스트를 만들어 각 리스트의 최댓값을 리턴하는 함수를 만들어 해결해보려고 했다.
• N이 작은 경우에는 문제없이 돌아갔지만 N이 커지면 너무 오랫동안 프로그램이 돌아가는 문제가 발생했다.
• 소인수를 구하는 함수에서 최대한 줄어보려고 했으나 실패하고 결국 인터넷의 힘을 빌렸다.
• 에라토스테네스의 체라는 알고리즘을 사용하면 시간단축이 엄청된다는 사실을 깨닫고 사용해서 풀어보았다.
• 에라토스테네스의 체를 이해하는데 조금 오래 걸린 문제….
• 
• 완성 코드: 1418