[알고리즘과 자료구조] JAVA - 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.


소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)


제한 조건

n은 2이상 1000000이하의 자연수입니다.


문제풀이

- 처음 아래와 같이 간단하게 해결하려고.. 풀었으나 실행시간에서 문제가 발생됐다.

두번째 for문에서 i가 j보다 작을때까지.. 반복문을 돌렸는데 이부분에서 시간이 오래걸린 것.

  1. class Solution {
  2. public int solution(int n) {
  3. int answer = 0;
  4. int count = 0;
  5. for ( int i = 2; i <= n; i++){
  6. // 2는 소수
  7. if( i == 2 ){
  8. answer++;
  9. continue;
  10. }
  11. // 3부터 소수 찾기 시작
  12. for( int j=2; j < i; j++){
  13. if ( i % j == 0 ){
  14. count++;
  15. break;
  16. }
  17. }
  18. if( count == 0 ) {
  19. answer++;
  20. }
  21. count = 0;
  22. }
  23. return answer;
  24. }
  25. }


j 값을 루트값으로 계산해서 다시 코드 작성.

- 실제로 위의 소스도 잘못된 데이터가 나오진 않지만 알고리즘은..... 참으로 복잡한 것..

  1. import java.util.*;
  2. class Solution {
  3. public int solution(int n) {
  4. int answer = 0;
  5. for ( int i = 2; i <= n; i++){
  6. int count = 0;
  7. for( int j=2; Math.pow(j, 2) <= i; j++){ // Math.pow(j, 2) 제곱근 구하기
  8. if ( i % j == 0 ){
  9. count++;
  10. break;
  11. }
  12. }
  13. if( count == 0 ) {
  14. answer++;
  15. }
  16. }
  17. return answer;
  18. }
  19. }
* 파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음
작성자 소개
최찬희 프로필
WrapUp 블로거

최찬희

반려견을 좋아하고, 차를 좋아하고, 여행을 좋아하고, 맛집을 찾아 즐기는 웹 개발자 입니다^^

댓글작성

관련 블로그 구경하기

작성자의 다른 포스팅