728x90 반응형 Sieve of Eratosthenes1 [정수론] 소수와 관련된 알고리즘 (소수 판정, 에라토스테네스의 체, 오일러 피 함수) 소수, 에라토스테네스의 체, 표준분해, 오일러 피 함수소수와 합성수 (primes and composites)소수: $1$과 자기 자신만을 약수로 가지는 수이다. 영어로 prime number라 하기 때문에 보통 $p$로 표기한다.합성수: $1$보다 큰 자연수 중에서 소수가 아닌 수. 약수의 개수가 3개 이상이다.※ $1$은 소수도 아니고 합성수도 아닌 수이다. $1$을 소수로 분류하면 소인수분해가 유일하지 않기 때문인 것으로 보인다.※ 소수(prime number)의 발음은 '소쑤'이고, 소수(decimal notation)의 발음은 '소:수'이다. $p \le \sqrt{n}$인 모든 소수 $p$에 대하여 $p$의 배수가 되는 합성수들을 모두 제거한 나머지는 모두 소수이다.따라서 $n=46$의 소수.. 2024. 8. 11. 이전 1 다음 728x90 반응형
