[알고리즘] 소수(prime number) 구하기 _에레스토테네스의 체
소수 구하기 에라스토테네스의 체 소수(priime_number)란? 어떤수의 약수가 1과 자기자신만 가지는 수 ex) 2, 3, 5, 7, 11, 13, 17, ... 소수가 아닌 수의 특징은 자기자신과 1이 아닌 다른수로 나누어 떨어질 수 있다. 즉 1과 자기자신이 아닌 다른수의 곱으로 나타낼수 있다. ex) 17 ( 소수 ) : 1 * 17 ex) 12( 소수아님) : 1 * 12, 2 * 6, 3 * 4, 4 * 3, 6 * 12, 12 * 1 에라스토테네스의 체 100개의 배열을만들고 모두 0으로 초기화 0번째방, 1번째 은 제외하고 2번째 방부터 값이 0이면 소수로 판단 출력한다. 출력후 그 해당하는 값의 배수를 모두 1로 바꾼다. 반복... 루프의 속도를 개선해보자. 2를 제외한 짝수는 절대 ..
Algorithm
2023. 7. 18. 18:15