danc
danc*dev
danc
  • 분류 전체보기
    • codestates_BE_bootcamp39
      • 주단위 일기
      • 회고
    • programming
      • JAVA
      • SPRING
      • GENERAL
      • LINUX
      • ALGORITHM
      • ERROR_HANDLING
    • web
      • NETWORK
      • DB
      • HTML
      • CSS
    • kr
    • nz

최근 글

인기 글

태그

  • 윈도우 11 우분투
  • 회고
  • 코드스테이츠 백엔드
  • TIL일기
  • 일기
  • TIL
  • HTTP
  • React에서 Authorization헤더
  • css
  • TIL 일기
  • 코드스테이츠
  • AOP

최근 댓글

티스토리

hELLO · Designed By 정상우.
danc
programming/JAVA

입력받은 자연수의 소수 판별

programming/JAVA

입력받은 자연수의 소수 판별

2022. 5. 8. 23:28

코드스테이츠 코플릿 문제 中

  • 자연수 num을 입력받고, num이 소수인지의 여부를 판별 해 boolean으로 반환한다.
  • 먼저 if문으로 필터링을 한다. 
  • 2는 소수이므로 바로 true, 1 이거나 2로 나눴을때의 나머지가 0 인지 확인

 

내가 한 방법

{

// 2는 소수라 바로 true를 리턴한다.
if ( num == 2)  
return true;


// 1이거나 2로 나눴을 떄 나머지가 0 이면 소수가 아니므로 false를 리턴한다.
if (num == 1 || num % 2 == 0)  
return false;


// 2부터 입력받은 자연수 사이의 모든 숫자를 하나씩 나눠서 나머지가 0인지 판별
for (int i = 2; i <num; i++) 
{
if(num % i == 0) return false;
}

//위 for문을 빠져 나오는 경우, 해당 자연수는 소수이다.
return true;
}

위와 같은 코드는 작동은 잘 되지만 입력받은 자연수가 큰 경우에는 속도가 느리다는 단점이 있다. 만약 입력받은 자연수가 200억이라면?

 


 

더 효율적인 방법

조금 더 효율적으로 코드를 짜 본다면 위의 for문을 입력받은 수의 제곱근을 응용해서 동작 속도를 절반가량 줄일 수 있다. for문을 제외한 코드는 위와 동일하다.

for ( int i = 3; i <= (int)(Math.sqrt(num)); i+= 2)
{
if(num % i == 0) 
        return false;
}

// 짝수는 위의 if문에서 전부 필터링 했으므로 홀수만 확인하면 된다.

// 대칭이 되는 패턴이 있다. 
// 예) 숫자 81은 [1 3 9 27 81] 의 약수를 갖는데, 제곱근 9를 기준으로 대칭을 이룬다.

// 따라서 제곱근을 기준으로 앞부분만 확인해도 전체를 돈 것과 같은 결과가 나온다.
저작자표시 (새창열림)

'programming > JAVA' 카테고리의 다른 글

Java - 필드와 변수  (0) 2022.05.10
Java - 클래스와 객체  (0) 2022.05.10
Java - Output / Input  (0) 2022.05.04
Java - 연산자 우선순위 (Operator Precedence) 테이블  (0) 2022.05.04
Java - Type  (0) 2022.05.04
  • 내가 한 방법
  • 더 효율적인 방법
'programming/JAVA' 카테고리의 다른 글
  • Java - 필드와 변수
  • Java - 클래스와 객체
  • Java - Output / Input
  • Java - 연산자 우선순위 (Operator Precedence) 테이블
danc
danc
Backend 개발자를 목표로 공부 중 입니다.

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.