ps:뫼비우스_함수
뫼비우스 함수 (Mobius function)
1부터 n까지의 뫼비우스 함수값을 모두 구하기
- 에라토스테네스의 체를 이용해서 구현 가능
- 리니어 시브를 이용해서 구현 가능
- ⇒ 이쪽이 더 빠르다. 소수 목록을 구할때 에라토스테네스의 체가 더 빠른 이유는 파이썬에서 slice assignment 가 빠르기 때문인데. 뫼비우스 함수값을 구할때는 어차피 slice assignment가 불가능하기때문에, 그냥 리니어시브를 쓰는게 더 빠르다.
- wheel optimization도 적용 가능하다
ps/뫼비우스_함수.txt · 마지막으로 수정됨: 2024/05/13 12:14 저자 teferi
토론