1.문제
2.풀이
에라토스테네스 체를 이용해서 문제를 풀었다. 에라토스네테스의 체는 소수를 구하는 알고리즘으로 이중포문을돌려 특정 숫자를 해당 숫자 이하의 모든숫자로 나누는(좀더 시간을 줄이려면 제곱근 이하의 숫자로 나누면됨) 경우보다 훨씬 적은 시간에 소수들을 찾아 낼 수 있다.
원리는 n의 배수에 해당하는 숫자를 하나씩 지워나가고 만약 이미 지운숫자면 넘어가는 방식을 계속해서 반복해 결국 소수들만 남게 하는 방법이다.
4948번
1.문제
2.풀이
에라토스테네스 체를 이용해서 문제를 풀었다. 에라토스네테스의 체는 소수를 구하는 알고리즘으로 이중포문을돌려 특정 숫자를 해당 숫자 이하의 모든숫자로 나누는(좀더 시간을 줄이려면 제곱근 이하의 숫자로 나누면됨) 경우보다 훨씬 적은 시간에 소수들을 찾아 낼 수 있다.
원리는 n의 배수에 해당하는 숫자를 하나씩 지워나가고 만약 이미 지운숫자면 넘어가는 방식을 계속해서 반복해 결국 소수들만 남게 하는 방법이다.