<5 kyu> Gap in Primes

<5 kyu> Gap in Primes

The prime numbers are not regularly spaced. For example from 2 to 3 the gap is 1. From 3 to 5 the gap is 2.

From 7 to 11 it is 4. Between 2 and 50 we have the following pairs of 2-gaps primes: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43

A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes

(see: http://mathworld.wolfram.com/PrimeGaps.html).

We will write a function gap with parameters:

g (integer >= 2) which indicates the gap we are looking for

m (integer > 2) which gives the start of the search (m inclusive)

n (integer >= m) which gives the end of the search (n inclusive)

In the example above gap(2, 3, 50) will return [3, 5] or (3, 5) or {3, 5} which is the first pair between 3 and 50 with a 2-gap.

So this function should return the first pair of two prime numbers spaced with a gap of g between the

limits m, n if these numbers exist otherwise nil or null or None or Nothing (depending on the language).

In C++ return in such a case {0, 0}. In F# return [||]

#Examples: gap(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7}

gap(2, 5, 5) --> nil. In C++ {0, 0}. In F# [||]

gap(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}

([193, 197] is also such a 4-gap primes between 130 and 200 but it's not the first pair)

gap(6,100,110) --> nil or {0, 0} : between 100 and 110 we have 101, 103, 107, 109 but 101-107is not a 6-gap

because there is 103in between and 103-109is not a 6-gap because there is 107in between.

소수는 규칙적으로 간격을 두지 않습니다. 예를 들어, 2에서 3 사이의 간격은 1입니다. 3에서 5 사이의 간격은 2입니다. 7에서 11 사이의 간격은 4입니다.

2와 50 사이에 다음과 같은 2 간격 소수 자릿수가 있습니다. 3-5, 5-7 , 11-13, 17-19, 29-31, 41-43

길이 n의 프라임 갭은 두 개의 연속 소수 사이에서 n-1 개의 연속 된 합성 수의 연속입니다

(http://mathworld.wolfram.com/PrimeGaps.html 참조).

우리는 매개 변수와 함수 간격을 작성합니다 :

g (정수> = 2) 우리가 찾고있는 간격을 나타냅니다.

검색 시작 (m 포함)을 제공하는 m (정수> 2)

검색 끝을 나타내는 n (정수> = m) (n 포함)

위의 예제에서 갭 (2, 3, 50)은 3과 50 사이의 첫 번째 쌍인 [3, 5] 또는 (3, 5) 또는 {3, 5}를 2 간격으로 반환합니다.

따라서이 함수는 n, null 또는 None 또는 Nothing (언어에 따라 다름)이 존재하는 경우 한계 m, n 사이에 g 간격으로 간격을두고있는 두 개의 소수의 첫 번째 쌍을 반환해야합니다.

C ++에서는 이러한 경우 {0, 0}을 반환합니다. F #에서 [||]를 반환합니다.

#Examples : gap (2,5,7) -> [5,7] 또는 (5,7) 또는 {5,7}

gap (2, 5, 5) -> nil. C ++에서 {0, 0}. F # [||]

gap (4, 130, 200) → [163, 167] 또는 (163, 167) 또는 {163, 167}

([193, 197]도 130과 200 사이의 4 갭 소수점이지만 첫 번째 쌍은 아니다)

갭 (6,100,110) -> nil 또는 {0, 0} : 100과 110 사이에 101,103,107,109가 있지만 101-107 사이에는 103in이 있고

103-109는 6 갭이 아니기 때문에 6 간격이 아닙니다. 왜냐하면 그 사이에 107in이 있기 때문입니다.

소수구할때 for(var j = 2; j <= i; j++) 로 하면 시간이 초과되서 final 통과가 안됬는데

에라토스테네스의 체로 풀면 for(var j = 2; j * j <= i; j++)

1차 테스트에서 7초 걸린던게 0.4초로 줄어듬.

수학 공부도 중요하구나...

혼자놀기