C# 소수값 구하기

소수 구하는 로직 정리

 

1은 소수값이 아니므로 2부터 시작을하며, 

 

입력된 숫자의 값보다 작은 수들로 몫을 구했을 때 0이 나오면 소수가 아니다.

 

예를 들어, input : 7을 처리한다하면

 

7%2!=0, 7%3!=0, 7%4=0, 7%5!=0, 7%6!=0을 먼저 해보고 나누어 떨어지지 않는 수에서 

 

해당 숫자들에 대해 다시 for문을 돌며 해당 숫자들 중 소수값을 찾는다.

 

찾는 과정 중에서 for문 조건식에서 2로 나눈 이유는, 4이상의 수 중에서 자신의 절반 값까지는

 

어떤 수로 나누어도 떨어지지 않는 수이기때문에 반복횟수를 줄이기 위해 2로 나누었다.

 

2로 나누지않고 for(int i=2; i< n; i++)로 해도된다.

 

=====소스=====

using System;
using System.Collections.Generic;
using System.Text;

namespace ProblemSolution
{
    class Program
    {


        static void Main(string[] args)
        {
            int input = int.Parse(Console.ReadLine());

            int cnt = 0;
            for (int i = 2; i <= input; i++)
            {
                if (IsPrime(i))
                {
                    //Console.WriteLine(i);

                    //가시화를 위해 WriteLine 말고 \t 사용
                    Console.Write("{0}\t", i);
                    cnt++;
                }

            }

            Console.WriteLine();
            Console.WriteLine("2부터 {0}번 까지의 약수  : {1}개", input, cnt);

            Console.ReadKey();
        }

	//소수값인지 확인
        public static bool IsPrime(int n)
        {
            bool isBool = true;
			            
            for (int i = 2; i <= n / 2; i++)
            {
                if (n % i == 0)
                {
                    isBool = false;

                    break;
                }

            }

            return isBool;
        }

    }
}

 

=====결과=====