소수찾기

이준경·2021년 5월 16일
코딩테스트
0

<나의풀이>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package CodingTest;
class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] prime= new boolean[n+1];
 
        prime[0] = true;
        prime[1] = true;
 
 
        for(int i=2; i*i<=n; i++) {         
            for(int j=i*i; j<=n; j+=i) {
                prime[j] = true;
            }
        }
 
        for(int i=0; i<=n; i++) {
            if(prime[i] == false) {
                answer +=1;
            }
        }
        return answer;
        }
}
cs
  1. n+1 만큼의 길이를 가진 boolean배열 생성 0과 1은 소수가 아니므로 true 대입.
  2. 주어진 i의 제곱은 소수가 아니므로 true 대입 반복
  3. false인 경우 소수이므로 answer증가 반복
  4. answer 반환
profile
이준경
이전 포스트

시저암호

다음 포스트

n개의 최소공배수

0개의 댓글

관련 채용 정보