[JAVA] 백준_2581

2581번: 소수 (acmicpc.net)

2581번: 소수

[문제]

처음에는 '에라토스테네스 체 알고리즘'을 몰라서 그냥 반복문으로 하나씩 나눠서 나머지가 0인 숫자가 2개인 걸로 소수를 구했다. 근데 에라토스테네스 체 알고리즘을 알게되었고, boolean 타입의 배열을 생성하고 소수면 false 소수가 아니면 true를 이용해 문제를 해결했다. 

1. 처음 풀이

[문제 설명] 

배열의 크기를 알 수 없으므로 Integer type의 ArrayList를 생성한다.

약수의 개수(count)가 2개면 ArrayList al에 하나씩 더해 원소(소수)를 채워나간다.

al이 비어있으면 -1을 출력하고 그렇지 않으면 al의 크기만큼 반복문을 돌려 sum과 min을 구한다.

2. 에라토스테네스 체 알고리즘을 이용한 풀이 

구글링 해보았더니 에라토스테네스 체 알고리즘을 이용한 풀이가 훨씬 빨랐다.

(원하는 숫자+1) 크기의 boolean 타입 배열을 생성하고 에라토스테네스 체 알고리즘 함수를 이용해 소수가 아닌 부분을 전부 true로 바꾼다. 

+ 에라토스테네스 체 알고리즘은 <소수가 되는 수의 배수를 지우면 남은 건 소수가 된다> 라고 생각하는 알고리즘이다.

소수가 무엇인지 찾을 필요 없이 2부터 자기 자신을 제외한 배수가 되는 것을 지우면 된다.

if문으로 소수인지 파악하고 소수면 sum에 i값(prime[i]는 boolean type)을 더한다.

시간이 훨씬 단축된다.

더 좋은 풀이가 있다면 알려주세요!