[C#]소수 찾기

프로그래머스 문제

 

문제 설명

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

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

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

처음 풀은 답

public class Solution {
    public int solution(int n) {
        int answer = 0;
        bool check = true;
        for(int i=2; i<=n; i++){
          check = true;
          for(int j = 2; j*j <= i; j++){
            if(i % j == 0){
              check = false;
              break;
              }
            } 
          if(chkeck==true)
          {
           answer++; 
           } 
         } 
       return answer; 
       }
    }

처음 풀은 답에서는 소수인지를 체크하는 bool형 변수 하나를 두고 이중 반복문을 돌려 처리했었다.

하지만 이렇게 하니 효율성 체크에서 실격 처리 되었다.

 

두번째 풀이

에라토스테네스의 체를 활용한 소수찾기 코드
(위의 코드보다 실행속도 10배이상 빨라짐 --> Math.Sqrt(num) 사용의 중요성)

소수찾기가 의외로 너무 어려워서 다른 사람의 코드를 참고하여 풀었다.

using System;
public class Solution {
    public int solution(int n) {
        int answer = 0;
        bool[] sosu =new bool [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;
    }
}

느낀점: 소수 찾는 문제가 생각보다 어려웠다.

 bool형 배열을 주어진 숫자 n보다 1크게 만든 후 , 위의 형식과 같이 첫 for문이 도는 시점에 true로 체크해주었고

크게 달라진 점은 이중반복문에서 반복의 범위를 n의 제곱근 까지만 해주었다.

 

 

0

 

에라토스테네스의 체 방식

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.