Coding Test/.... (1) 썸네일형 리스트형 [알고리즘] 소수 판별 알고리즘 1. O(√n) 2부터 √n까지 나눠서 나머지가 0이 아니면 소수다. ∵ 만약 √n 이후에 나눠서 나머지가 0이 되는 수가 있다면, 그 수와 1~√n 사이의 수랑 곱해져서 n이 되는데, 그전에 필터링이 되지 않았다는 뜻이므로 이는 모순이다. bool isPrimeNum(int n) { if (n == 1) return false; else if (n == 2) return true; else if (n%2 == 0) return false; else { for (int i=3; i*i 이전 1 다음