사용자 도구

사이트 도구


ps:뫼비우스_함수

뫼비우스 함수 (Mobius function)

1부터 n까지의 뫼비우스 함수값을 모두 구하기

  • 에라토스테네스의 체를 이용해서 구현 가능
  • 리니어 시브를 이용해서 구현 가능
    • ⇒ 이쪽이 더 빠르다. 소수 목록을 구할때 에라토스테네스의 체가 더 빠른 이유는 파이썬에서 slice assignment 가 빠르기 때문인데. 뫼비우스 함수값을 구할때는 어차피 slice assignment가 불가능하기때문에, 그냥 리니어시브를 쓰는게 더 빠르다.
    • wheel optimization도 적용 가능하다

토론

댓글을 입력하세요:
E T O T A
 
ps/뫼비우스_함수.txt · 마지막으로 수정됨: 2024/05/13 12:14 저자 teferi