Hippo's data

오늘은 소수 찾기 알고리즘에 대해 포스팅 하겠다!!  소수란 무엇일까? 자연수를 분류하자면  1, 소수, 합성수로 나뉜다.  소수(prime number) = 약수로 1과 자기자신만을 가지는 수 = 약수를 2개만 가지는 수 예) 2,3,5,7,9 ...  -> 1과 자기자신을 제외한 자연수로 나누어 떨어지지 않음  합성수(composition number) = 약수로 1과 자기자신 이외의 수를 가지는 수 = 약수를 3개 이상 가지는 수  예) 4,6,8,10 ...소수 찾기를 간단한 코드로 구현하면 시간복잡도는 약 O(n)을 가지게 된다즉, 소수를 찾을 때  약  n번을 나누며 확인해야 하므로 시간복잡도가 클 수 있다 이를 보완한 방법이  에라토스테네스의 체(Eratosthenes' Sieve)이다. #..