소수
-
[WEEK01/DAY01] 백준 문제 : 소수 찾기SW Jungle/TIL (Today I Learned) 2022. 9. 24. 02:24
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 오늘 풀었던 알고리즘 중에 제일 어려웠던 문제다. 소수는 약수가 1과 자기 자신밖에 없는 1보다 큰 자연수를 말한다. 그래서 1보다 큰 자연수 n이 주어졌을 때 n이 소수인지를 판별하는 가장 간단한 방법은 2에서 n-1 까지의 모든 자연수로 나누어 보는 것이다. 만약 한 경우에라도 나누어 떨어진다면, n은 소수가 아닌 것이다. 위 방법으로 풀이하면 시간 복잡도가 O(N)이 된다. 좀 더 빠른 방법이 있는데, 굳이 2에서 n-1까지 반복하지 않고 √n 까지만 반복해도..