1 unstable release
0.1.1 | Apr 13, 2022 |
---|---|
0.1.0 |
|
#1092 in Algorithms
16KB
161 lines
rust-eratos
An implementation of 'Sieve of Eratosthenes' for rust language practice.
Usage
cargo install rust-eratos
rust-eratos 11
Rust 언어에 적응하기
이 문서의 목표
- Rust 언어에 대한 기본적인 이해를 마친 초심자에게
- 언어를 직접 사용하며 몸에 익히고 적응하는데 도움을 주고자
- 가볍게 따라할 수 있는 작은 목표들을 단계적으로 제공한다.
사전 지식
- Rust 언어의 기본 문법을 대략적으로 알고 있거나 쉽게 찾아볼 수 있어야 한다.
- 혹시나 처음이라면 취향에 맞는 것으로 준비한다.
- 짧지만 맛보기는 가능한 마소 런 튜토리얼 Rust First Steps
- 길지만 훌륭한 공식 커뮤니티 튜토리얼 The Rust Programming Language
- 온라인 강의 Exercism: Rust Track
- 유툽 강의 YouTube: mithradates
- 혹시나 처음이라면 취향에 맞는 것으로 준비한다.
- 소수(prime number)를 판별하는 간단한 알고리즘 지식이 필요하다.
- 미리 학습할 필요는 없고, 따라하면서 필요한 내용을 찾아본다. 소수 (수론)
지금 단계에서 집중해야 할 것
- 기본 문법을 완전히 습득하는 것
- primitive types, variable, if, match, for, println!, fn, ...
- 기본 자료구조들에 익숙해지는 것
- array, slice, String, Vec, HashMap, tuple, ...
- 언어 공통적 요소를 사용해보는 것
- struct, enum, trait, iterator, ...
- 언어 특수한 요소를 경험하고 이해하는 것
- ownership, borrow, reference, macros, ...
- 언어 생태계를 경험하는 것
- cargo, crates, ...
- 이번 따라하기에서 위의 것들을 전부 사용해보는 것은 아님
지금은 집중하지 않을 것
- 알고리즘의 개선
- 특정 프레임워크의 사용 방법
- 언어와 생태계의 고급 기능들
- generic, polymorphism, thread, future, async, cargo workspace, ...
따라하기
- 제시된 함수의 내용을 구현한다.
- 만약 알고리즘을 잘 이해하지 못하겠고 생각하기도 귀찮다면, 문서 하단의 예시 코드를 적절하게 포팅하는 방식으로 따라한다.
- 제공된 인터페이스들은 입력 받은 수 n을 포함하지 않는 결과를 리턴하도록 의도하였으나, 포함시켜도 무관하다. 다만 일관된 동작으로 작성한다.
n 이 소수인지 판별하기
fn is_prime_number(n: u32) -> bool
- 혹시 if, for 명령들로만 구현했다면 match, range, iter, any 등을 이용한 표현으로 구현해본다.
n 미만의 소수의 수를 구하기
fn get_prime_number_count_below(n: u32) -> usize
- 혹시 if, for 명령들로만 구현했다면 match, range, iter, filter, count 등을 이용한 표현으로 구현해본다.
- filter를 사용했다면 앞에서 사용했던 any의 것과 비교하여 타입의 차이와 그 이유를 알아본다.
- hint: Iterator::next(&mut self) vs new iterator
n 미만의 가장 큰 소수를 구하기
fn get_largest_prime_number_below(n: u32) -> u32
- 혹시 if, for 명령들로만 구현했다면 match, range, iter, find, Option<T> 등을 이용한 표현으로 구현해본다.
- find를 사용했다면 앞에서 사용했던 any, filter들과 비교하여 타입의 차이와 그 이유를 알아본다.
n 미만의 소수들을 구하기
fn get_prime_numbers_below(n: u32) -> Vec<u32>
- 에라토스테네스의 체 알고리즘을 구현한다.
- 기본 자료구조 중 Vec을 사용하여 구현해본다.
- 혹시 if, for 명령들로만 구현했다면 range, into_iter, filter, collect 등을 이용한 표현으로 구현해본다.
n을 커맨드 라인 입력을 정수로 변환하기
fn parse_args(args: &[String]) -> Result<u32, &'static str>
- 커맨드 라인으로 입력받은 문자열을 정수로 변환한다.
- 정수 변환 결과와 오류를 Result<T, E> 를 이용하여 적절하게 반환하고 처리해본다.
작성한 기능들로 stdout에 출력하기
# output example
> rust-eratos 13
13 is a prime number.
There are 5 prime numbers less than 13, and the largest number is 11.
Prime numbers less than 13.
[2, 3, 5, 7, 11]
더 해보기
- 유닛 테스트 작성하기
- 구현된 기능들을 라이브러리로 만들기
- 계산된 결과를 캐싱하여 성능 개선하기
- 코드의 실행 속도를 프로파일하고 개선하기
- {2, 3, 5} 휠 인수분해 알고리즘 적용하기
예시 코드
# python
import sys
def is_prime_number(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1): # (n ** 0.5) == (math.sqrt(n))
if n % i == 0:
return False
return True
def get_prime_number_count_below(n):
if n < 3:
return 0
count = 0
for i in range(2, n):
if is_prime_number(i):
count += 1
return count
def get_largest_prime_number_below(n):
for i in reversed(range(2, n)):
if is_prime_number(i):
return i
return 0
def get_prime_numbers_below(n):
# sieve = [0, 0] + [i for i in range(2, n)]
sieve = [0, 0]
for i in range(2, n):
sieve.append(i)
for i in range(2, int(len(sieve) ** 0.5) + 1):
if sieve[i] <= 0:
continue
index = i * i
while index < len(sieve):
sieve[index] = 0
index += i
primes = []
for i in range(2, len(sieve)):
if sieve[i] > 0:
primes.append(i)
return primes
# return [i for i in range(2, len(sieve)) if sieve[i] > 0]
def main(n):
print(f"{n} is a prime number.")
print(f"There are {get_prime_number_count_below(n)} prime numbers less than {n},"
f" and the largest number is {get_largest_prime_number_below(n)}")
print(f"Prime numbers less than {n}")
print(get_prime_numbers_below(n))
if __name__ == "__main__":
main(int(sys.argv[1]))