[BOJ] 2581 소수

 

 

//소수는 1과 자기자신만을 약수로 가지고있으므로 2부터 n-1 까지 수로 나눠지면 안되는 성질을 가지고있다.
//2,3,5,7,11,13,17....

 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace smilejsu
{
    class Program
    {
        //모든경우의 수를 검사하는 방법.
        //O(N)의 시간 복잡도를 가지고있으므로 파라미터값이 커질수록 시간값또한 커지게 된다.
        
        static bool isPrime(int num)
        {
            if (num == 1) return false;
            
            for (int i = 2; i < num; i++)
            {
                if (num % i == 0) return false;
            }

            return true;
            
        }
        
        
        
        // O(N^(1/2))시간 복잡도를 가진 방법으로 계산의 양이 기본방법보다 줄어든다.
        // 그 이유는 모든 약수들은 대칭을 이루는 성질을 이용하여 제곱근까지만 약수의 여부를 검증하면
        // 그보다 큰 약수의 수는 검사할 필요가 없어진다
        
        public bool CalcPrime(int num) 
        {
            int nr = (int)Math.Sqrt(num); 
            for (int i = 2; i <= nr; i++) 
            {
                if (num % i == 0)
                    return false; 
            } 
            return true; 
        }
        
        
        // 에라토스테네스의 체
        // 에라토스테네스의 체는 가장 대표적인 소수판별 알고리즘 이며 많은 양의 소수를 가장 빠르고 정확하게
        // 구하는 알고리즘이다.
        // 2부터 시작하여 자기자신을 제외한 나머지약수들을 다 지우며 나가며 결과적으로는 소수만 남게된다.
        void Eratosthenes(int num)
        {
            int[] temp = new int[num + 1];
            for(int i=2;i<num;i++)
            {
                temp[i] = i;
            }
            for(int i=2;i<=num;i++)
            {
                if (temp[i] == 0) continue;
                for(int j=i+i; j<= num; j+=i)
                {
                    temp[j] = 0;
                }
            }
        }

        static void Main(string[] args)
        {
            int m = int.Parse(Console.ReadLine());
            int n = int.Parse(Console.ReadLine());
            
            List<int> list = new List<int>();
            for (int i = m; i <= n; i++)
            {
                //Console.WriteLine("{0} : {1}", i, isPrime(i));
                if (isPrime(i))
                    list.Add(i);
            }

            if (list.Count > 0)
            { 
                var sum = list.Sum();
                Console.WriteLine(sum);
                var min = list.Min();
                Console.WriteLine(min);
            }
            else
            {
                Console.WriteLine(-1);
            }




        }
    }
}