[EP 050] 연속된소수의합이 다시 소수

무식한 방법으로 푼다. 루프를 빠져나오는 조건을 잘 줘야 빨리 끝난다. 소수를 구할 때, 나눌 수가 소수후보의 제곱근보다 크다면 빠져나오라는 조건을 빼면 시간이 하염없이 걸리고, 연속된소수의 합이 다시 소수인 모든 수를 구하는 것이 아니고, 그 소수 갯수의 최대값을 구한다는 조건을 for 루프에 잘 적용하면 또 시간을 더 단축할 수 있다. 물론 깔끔함은 훼손되지.

/*
 * http://projecteuler.net/index.php?section=problems&id=50

    Problem 50
    15 August 2003

    The prime 41, can be written as the sum of six consecutive primes:
    41 = 2 + 3 + 5 + 7 + 11 + 13

    This is the longest sum of consecutive primes that adds to a prime 
    below one-hundred. The longest sum of consecutive primes below 
    one-thousand that adds to a prime, contains 21 terms, and is equal 
    to 953.

    Which prime, below one-million, can be written as the sum of the 
    most consecutive primes?

 *  백만보다 작은 소수 중에서 어느 것이 가장 많은 연속된 소수의 합으로 표현될 수
 *  있나?

 */

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

namespace ep50
{
    class Program
    {
        private static int 최대값 = 1000000;
        private static List<int> 소수리스트 = new List<int>();

        static void Main(string[] args)
        {
            모든소수구한다();
            연속된소수합이소수인경우찾자();
        }

        static void 모든소수구한다()
        {
            int[] 잘아는소수 = { 2, 3, 5, 7, 11, 13 };
            foreach(int 소수 in 잘아는소수)
                소수리스트.Add(소수);

            for(int 소수후보 = 17 ; 소수후보 < 최대값 ; 소수후보 += 6)
            {

                if (소순가(소수후보))
                {
                    소수리스트.Add(소수후보);
                }
                if(소순가(소수후보 + 2))
                    소수리스트.Add(소수후보+2);
            }

        }

        static bool 소순가(int 소수후보)
        {
            foreach (int 소수 in 소수리스트)
            {
                if (소수후보 < 소수 * 소수)
                    break;

                if (소수후보 % 소수 == 0)
                    return false;
            }
            return true;
        }

        static void 연속된소수합이소수인경우찾자()
        {
            int 시작인덱스 = 0, 끝인덱스 = 0;
            int 소수합 = 0;
            int 소수개수, 소수개수최대값 = 1;
            for(시작인덱스 =  0; 시작인덱스 < 소수리스트.Count(); 시작인덱스++)
                for (끝인덱스 = 시작인덱스 + 소수개수최대값 - 1; 끝인덱스 < 소수리스트.Count(); 끝인덱스++)
                {
                    소수합 = 연속소수합(시작인덱스, 끝인덱스);
                    소수개수 = 끝인덱스 - 시작인덱스 + 1;
                    if(소수개수 > 소수개수최대값) {
                        if (소수합 > 최대값)
                            break;
                        if (소수리스트.Contains(소수합) && 소수개수최대값 < 소수개수)
                        {
                            소수개수최대값 = 소수개수;
                            Console.WriteLine("{0} = {1} + ... + {2}, {3} 개",
                                소수합, 소수리스트[시작인덱스], 소수리스트[끝인덱스], 소수개수);
                        }
                    }

                }
        }

        static int 연속소수합(int 시작인덱스, int 끝인덱스)
        {
            int 소수합 = 0;
            for(int i = 시작인덱스; i <= 끝인덱스; i++)
            {
                소수합 += 소수리스트[i];
            }
            return 소수합;
        }
    }
}