'소수찾기' 태그의 글 목록

소수찾기

소수 찾기 /프로그래머스/자바/level1/에라토스테네스의 체 2020.02.05

소수 찾기 /프로그래머스/자바/level1/에라토스테네스의 체

2020. 2. 5. 09:56

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기 | 프로그래머스

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 1000000이하의 자연수입니다. 입출력 예 n result 10 4 5 3 입출력 예 설명 입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환 입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재

programmers.co.kr

<소수 찾기 >

○ 처음 푼 풀이

변수 2개 사용한 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
  public int solution(int n) {
      int answer = 0;
      int count =0;//소수판별 변수
      int  primeNum=1;//소수개수 반환변수
     
      for(int i=3; i<=n;i++){//3부터 n까지
         for(int j=2; j<i; j++){
              if(i%j==0)
                  count++;
 
          }
          if(count==0)
                  primeNum++;
          count=0;
      }
           return answer=primeNum;
  }
}
 
Colored by Color Scripter


 
○ 변수 하나 사용한 풀이

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
  public int solution(int n) {
      int answer = 1;
      int count =0;//소수판별 변수
     
      for(int i=3; i<=n;i++){//3부터 n까지
         for(int j=2; j<i; j++){
              if(i%j==0)
                  count++;
            }
          if(count==0)
                answer++;
          count=0;
      }
           return answer;
  }
}
 
Colored by Color Scripter

cs

- 이렇게 푸니깐 효율성 검사랑 테스트 10, 11이 시간초과로 안된다
- 에라토스테네스 체? 를 사용하라는데 잘 모르겠다 다시 풀어봐야겠다.
 
 
○ 에라토스테네스 체를 이용한 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
  public int solution(int n) {
      int answer = 0;
      boolean[] sosu =new boolean [n+1];
      
      for(int i=2; i<=n ; i++)
          sosu[i]=true;
       //에라테네스   
      int root=(int)Math.sqrt(n);
      
     for(int i=2; i<=root; i++){
         if(sosu[i]==true){
             for(int j=i; i*j<=n; j++)
                    sosu[i*j]=false;
         }      
     }
      for(int i =2; i<=n; i++)  { 
          if(sosu[i]==true)
          answer++;
      }
      return answer;
  }
}
      
Colored by Color Scripter

cs

에라토스테네스의 체 아이디어
1. 자신의 값의 루트 값을  구한다. 
2. 2부터 루트 값사이의 수들의 배수들을 다 없앤다
3. 그리고 나머지는 소수이다.

'JAVA > 프로그래머스' 카테고리의 다른 글

문자열을 정수로 바꾸기/java/substring()/Integer.parseInt() (0)	2020.02.07
수박수박수박수박수박수?/Java/프로그래머스 (0)	2020.02.07
서울에서 김서방 찾기 /Java/Level1/프로그래머스 (0)	2020.02.04
[ Java Level 1 ] 문자열 내 p와 y의 개수 (0)	2020.02.04
[Java Level 1]가운데 글자 가져오기 (0)	2020.02.03

PREV 1 NEXT

🔥아이티 부수기🔥

소수찾기

소수 찾기 /프로그래머스/자바/level1/에라토스테네스의 체

<소수 찾기 >

'JAVA > 프로그래머스' 카테고리의 다른 글

+ Recent posts

티스토리툴바