🤔5-Minute Guide! Coding Test Essential: Is It Prime? Easy Method Explained!

[@algorithm_brother]

소스 코드(java, cpp, py, js) :
github.com/hoonlucky7/algorithm/tree/master/basic/prime
💡소수 구하는 방법💡
소수 : 1과 자신만을 약수로 가지는 수
어떻게 소수인지 확인할까?
💡 √N까지의 수만 확인해도 소수를 판별
숫자 N이 소수인지 확인하려면, N을 1과 자기 자신 말고 다른 숫자로 나눔
만약 나누어떨어지는 숫자가 하나도 없으면 소수임
반복문을 써서 확인하기
N이 소수인지 확인하는 방법:
2부터 N−1까지의 숫자로 나눔
만약 나눌 때 나머지가 0인 숫자가 있으면 소수가 아님
나눌 때 나머지가 0인 숫자가 하나도 없으면 소수임
만약 N이 어떤 두 수 a와 b의 곱으로 표현될 수 있다면, 이 두 수 중 하나는 반드시 √N 이하여야 합니다. 그렇지 않으면 두 수의 곱이 N을 초과하기 때문입니다. 그래서 √N까지의 수만 확인해도 소수를 판별 가능
N=36일 때, 나눠지는 숫자를 찾는다고 생각 하자!
36=2×18
36=3×12
36=4×9
36=6×6
여기서 중요한 건:
2,3,4,6 중 하나는 항상 √36=6보다 작거나 같음
18,12,9처럼 큰 숫자는 √N​ 이하인 숫자로 이미 확인 가능
즉, √N​까지만 확인해도 N이 소수인지 충분히 알 수 있음
💡💡 에라토스테네스의 체
소수를 효율적으로 찾는 고대 알고리즘
제안자: 에라토스테네스 (고대 그리스 수학자)
핵심 아이디어:
소수는 1과 자기 자신만을 약수로 가짐
소수의 배수를 제거하면 남은 숫자가 소수
1. 1~50까지 숫자를 쭉 나열.
2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 50
2. 2는 소수이므로 2의 배수는 모두 제거.
2, 3, X, 5, X, 7, X, 9, X, ..., 49 (X는 제거된 숫자)
3. 다음 남은 숫자 중 3은 소수. 3의 배수는 모두 제거.
2, 3, X, 5, X, 7, X, X, X, ..., 49
4. 다음으로 남은 5는 소수. 5의 배수는 모두 제거.
2, 3, X, 5, X, 7, X, X, X, ..., X
5. 이 과정을 √50 이하의 수(7)까지 반복.
7의 배수 제거.
이미 제거된 숫자는 건너뜀.

[@Wssol]

알오빠 잘보고 있습니다 ~!

[@algorithm_brother]

@@Wssol 감사합니다^^

[@jinyoung6661]

오 잘 봣슴닷 :)

[@algorithm_brother]

@@jinyoung6661 감사합니다 :)

[@ppp5977]

알형 진자 잘 가르쳐준다

[@algorithm_brother]

@@ppp5977 감사합니다ㅎㅎ