프로그래머스 | 소수찾기

문제 설명

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

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

제한 조건

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

입출력 예

nresult

10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

public class Solution {
    public int solution(int n) {
        int answer = 0;
        return answer;
    }
}

 

 

using System;
using System.Linq;
 
namespace _17
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("소수찾기");
            //case 1 
            //int n = 10;
            //result: 4
 
            //case 2 
            int n = 5;
            //result = 3;
            var s = new Solution();
            var result = s.solution(n);
            Console.WriteLine(result);
        }
    }
 
    public class Solution {
        public int solution(int n) {
            int answer = 0;
            int[] arr = new int[n+1];
            for(int i = 2; i<=n; i++){
                arr[i] = i;
            }
 
            for(int i = 2; i<=n; i++){
                for(int j = 2; j<=n; j++){
                    if(arr[j] != i && arr[j] % i == 0){
                        arr[j] = 0;
                    }
                }
            }
 
            foreach(var prime in arr){
                Console.Write(prime + " ");
            }
 
            Console.WriteLine();
 
            answer = arr.ToList().Where(x=>x != 0).Count();
 
            return answer;
        }
    }
}
 

 

 

체크할 때, 모든 수를 다 돌면서 체크할 필요 없이 배수만큼만 반복문을 돌게하는 것이다.
그리고, 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다.
(왜냐면, 체크된 수의 배수들도 이미 다 체크가 되어있기 때문이다)
출처: https://marobiana.tistory.com/91 

[C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체

 

using System;
using System.Linq;
 
namespace _17
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("소수찾기");
            //case 1 
            int n = 10;
            //result: 4
 
            //case 2 
            //int n = 5;
            //result = 3;
 
            //case 3
            //int n = 100;
            //result = ?
            var s = new Solution();
            var result = s.solution(n);
            Console.WriteLine(result);
        }
    }
 
    public class Solution {
        public int solution(int n) {
            int answer = 0;
            int[] arr = new int[n+1];
            for(int i = 2; i<=n; i++){
                arr[i] = i;
            }
 
            for(int i = 2; i<=n; i++){
                
                if(arr[i] == 0) continue; //배수인지 체크 
 
                for(int j = i + i ; j<=n; j += i){
                    
                    if(arr[j] == 0) continue;
 
                    Console.WriteLine(arr[j] + " ---> 0");
                    arr[j] = 0;
                }
            }
 
            Console.WriteLine();
            Console.WriteLine("*******************");
 
            foreach(var num in arr){
                Console.Write(num + " ");
                if(num != 0){
                    answer++;
                }
            }
 
            Console.WriteLine();
            Console.WriteLine("*******************");
 
            //answer = arr.ToList().Where(x=>x != 0).Count();
 
            return answer;
        }
    }
}