연습문제
🔥 소수 찾기 🔥
👀 문제
1부터 입력받은 숫자 n사이에 있는 소수의 개수를 반환하는 함수 solution을 완성해보자.
소수는 1과 자기자신으로만 나누어지는 수를 의미함✔️ 조건
- n은 2이상 1000000이하의 자연수
👩💻 입력 & 🧙 출력
| n | return |
|---|---|
| 10 | 4 |
| 5 | 3 |
🙋♀️ 첫번째 풀이
import java.util.*;
class Solution {
public int solution(int n) {
List<List<Integer>> arr = new ArrayList<>();
int answer = 0;
for(int i=1;i<n+1;i++){
List<Integer> num = new ArrayList<>();
for(int j=1;j<i+1;j++){
if(i%j==0){
num.add(j);
}
}
arr.add(num);
if(arr.get(i-1).size()==2){
answer +=1;
}
}
return answer;
}
}- List안에 List인 중첩리스트 arr을 선언
- i의 반복문을 돌리면서 num이라는 리스트를 생성
- 소수를 구해서 num에 add해주고 arr에 num을 add 해줌
- 만약 arr의 size가 2와 같다면 소수라는 것이니까 answer에 +1을 해줌
이렇게 풀어서 테스트는 통과했는데!
효율성과 테스트 10,11,12에서 모두 시간초과가 발생했다 ㅠㅠ
🙋♀️ 두번째 풀이
질문하기에 많은 분들이 에라토스테네스의 체를 이용해야 통과를 할 수 있다고 한다.
가장 도움이 되었던 글과 코드를 바탕으로 다시 풀어보자면!!
- 모든 수를 배열에 대입해준다.
- 소수가 아니라면 해당 배열의 값을 0으로 변경해주고
- 소수라면 배열의 값을 유지한다.
이러한 방법으로 7까지 진행하고 나면 8,9,10은 이미 소수가아니라고 앞에서 정의했기 때문에 넘어갈 수 있고 덕분에 시간을 절약하게 됩니다.
class Solution {
public int solution(int n) {
int answer = 0;
int[] arr = new int[n+1];
for(int i=0;i<=n;i++){
arr[i] = i;
}
arr[1] = 0;
for(int i=2;i<=n;i++){
if(arr[i]==0)continue;
for(int j=i*2; j<=n; j+=i){
arr[j] = 0;
}
}
for(int i=0;i<arr.length;i++){
if(arr[i] != 0){
answer++;
}
}
return answer;
}
}- 길이가 n+1인 배열 arr을 선언
- 0부터 n까지의 값을 배열 arr에 대입
- 1은 소수가 아니기 때문에 0으로 설정
- 2부터 n까지의 반복분을 돌리면서
- 만약 arr의 i번째의 값이 0이라면 즉, 이전에 찾았던 소수의 배수값이라면 다음 수로 이동해서 반복문을 수행
- j의 값이 n보다 작거나 같을때까지 반복문을 돌리는데 i의 배수번째의 값에 0을 대입하는 것이다.
에라스토테네스의 체를 통해서 배수의 수는 소수가 아니라는 것을 알았기때문에 소수가 아닌 것에 0을 대입해서 소수를 찾는 방법이다. - arr의 길이만큼 반복하면서 arr의 i번째의 값이 0이 아니라면 answer에 ++를 해준다.
💬 다른 풀이
1. 제곱근을 이용한 풀이
class Solution {
public int solution(int n) {
int answer = 0;
for(int i = 2; i <= n; i++){
int j = 2;
int cnt = 0;
while(j <= (int)Math.sqrt(i)){
if(i % j == 0){ //나누어떨어지면 소수가 아님
cnt += 1; //소수가 아닐때 cnt에 +1
break; //break가 없으면 효율성 통과 불가능
}
j += 1;
}
if(cnt == 0) answer += 1;
}
return answer;
}
}- i를 2부터 n보다 작거나 같을때까지 반복문을 돌린다.
- j의 값은 2 cnt의 값은 0을 대입한다.
- j의 값이 i의 제곱근의 값보다 작거나 같은때 까지 반복문을 돌리면서
- 만약 i나누기 j의 나머지가 0이라면 cnt에 +1을 하고 break해준다.
- 그렇지 않다면 j에 값을 +1해준다.
- cnt의 값이 0이라면 answer에 +1
👏 마무리
에라토스테네스의 체...
소수를 저렇게 간단히 구할 수 있었다니
맘 먹으면 못할 게 없지