[백준] 2581번

문제출처: https://www.acmicpc.net/problem/2581

2581번: 소수

 

1978번처럼 소수를 찾아내서 요리하는 소수 시리즈다. 다만 1978에서 추가된 조건이 존재한다.

우선 1978번 문제의 내용을 조금 언급해볼까 한다.

​

한 줄에 띄어쓰기로 각각 나타난 N개의 숫자 중 소수를 찾고 그 개수를 세어 출력한다.

입력값으로는 첫째 줄에 숫자의 개수 N, 둘째 줄에 N개의 숫자들이 들어온다.

출력값으로는 그 중 소수의 개수를 출력하면 된다.

​

알고리즘에서 소수를 찾아내려면 소수의 정의를 알면 간단하다.

소수는 자기 자신과 1로만 나누어 떨어지는 숫자이다.

따라서 2 이상의 다른 숫자로 나누어진다면 그건 소수가 아니다.

이걸 반복문에 넣어주면 된다.

​

N번만큼 소수가 아니라면 error를 1, 소수라면 개수를 카운트해주는 것을 반복한다.

그리고 마지막으로 count값을 출력하면 된다.

​

 

이 코드를 응용하여 2581번을 풀면 간단하다.

​

2581번은 주어진 범위 내에서 소수인 숫자들을 찾아 합과 최솟값을 출력하는 문제다.

그 구간 내에 소수가 존재하지 않을 경우 -1만을 출력한다.

​

소수 중 최솟값을 찾기 위해 배열 num을, 소수의 합을 구하기 위해 변수 sum을 선언한다.

1978번과 동일하게 반복문을 돌린다. 다만 여기서 변경되어야 할 점이 있다.

소수로 판정된 경우 배열 num에 append하고, 그 소수의 값만큼 sum에 더해준다.

​

소수를 모두 찾은 후 반복문을 빠져나와 배열 num을 오름차순으로 정렬한다.

그럼 num[0]에 가장 작은 소수가 있으니 그것을 출력해주면 된다.

이건 어제 푼 2562번에서 다룬 내용과도 유사하다.

​

소수가 없는 경우 -1을 출력해야하므로 조건문을 작성한다.

소수가 없는 경우는 sum이 0인 경우이므로 그것을 조건으로 쓴다.

sum == 0 이면 -1, 그렇지않으면 sum과 num[0]을 차례로 출력한다.

이 코드로는 4620ms로 시간이 꽤 오래 걸렸다.

움...더 빠르게 알고리즘을 수행할 수 있는 방법은 아직 생각해보지 못함.

​