1978 (1) 썸네일형 리스트형 백준 js 1978: 소수 찾기 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 풀이 소수를 찾는 방법을 알면 쉽게 풀 수 있다. 소수는 2이상의 수 중, 나누어 지는 수(약수)가 자신과 1밖에 없는 수를 말한다. 그러면 해당 수를 n라고 하고, n가 소수인지 찾기 위해 루프문 내에서 하나씩 비교해보면 된다. 그렇게 되면 O(n)이 된다. 그러나 n = a * b (a √n => a * b > n a = b 이면 소수가 아니게 된다 (√n라는 수로 나누어지므로) 반대로 얘기하.. 이전 1 다음