목록골드바흐 (1)

문미새 개발일지

크래프톤 정글 week01, day07 - 알고리즘 문제 풀기

소수 1보다 큰 자연수 중 1과 자신만을 약수로 가지는 수 ex) 11은 1x11로만 성립되기 때문에 소수 ​ 에라토스테네스의 체 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 효율적으로 소수를 찾는 방법이다. 순서(100 이전의 소수를 모두 찾기) 1을 먼저 제거 2를 제외한 2의 배수 모두 제거 3을 제외한 3의 배수 모두 제거 5를 제외한 5의 배수 모두 제거 7을 제외한 7의 배수 모두 제거 ... 등 제거하고 남은 제일 낮은 수의 배수를 모두 제거하면 소수만 남는다. 일정 범위 내에서 구하기는 이 방법이 좋지만 특정 값이 소수인지 판별하는건 다른 알고리즘이 더 빠르다. 주어진 N개 중에 소수가 몇 개인지 찾기 주어진 N개의 소수를 받아 그 안에 소수가 몇 개인지 찾아야 한다. import..
크래프톤 정글/TIL 2024. 2. 19. 13:45
이전 Prev 1 Next 다음