Skip to content

3770. Largest Prime from Consecutive Prime Sum

Description

You are given an integer n.

Return the largest prime number less than or equal to n that can be expressed as the sum of one or more consecutive prime numbers starting from 2. If no such number exists, return 0.

 

Example 1:

Input: n = 20

Output: 17

Explanation:

The prime numbers less than or equal to n = 20 which are consecutive prime sums are:

  • 2 = 2

  • 5 = 2 + 3

  • 17 = 2 + 3 + 5 + 7

The largest is 17, so it is the answer.

Example 2:

Input: n = 2

Output: 2

Explanation:

The only consecutive prime sum less than or equal to 2 is 2 itself.

 

Constraints:

  • 1 <= n <= 5 * 105

Solutions

We can preprocess a list of all prime numbers less than or equal to \(5 \times 10^5\), then calculate the consecutive prime sums starting from 2, and store those sums that are prime numbers in an array \(s\).

For each query, we simply need to use binary search in array \(s\) to find the maximum value less than or equal to \(n\).

In terms of time complexity, preprocessing the primes takes \(O(M \log \log M)\) time, and each query takes \(O(\log k)\) time, where \(M\) is the upper limit of preprocessing, and \(k\) is the length of array \(s\). In this problem, \(k \leq 40\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
mx = 500000
is_prime = [True] * (mx + 1)
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, mx + 1):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, mx + 1, i):
            is_prime[j] = False
s = [0]
t = 0
for x in primes:
    t += x
    if t > mx:
        break
    if is_prime[t]:
        s.append(t)


class Solution:
    def largestPrime(self, n: int) -> int:
        i = bisect_right(s, n) - 1
        return s[i]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private static final int MX = 500000;
    private static final boolean[] IS_PRIME = new boolean[MX + 1];
    private static final List<Integer> PRIMES = new ArrayList<>();
    private static final List<Integer> S = new ArrayList<>();

    static {
        Arrays.fill(IS_PRIME, true);
        IS_PRIME[0] = false;
        IS_PRIME[1] = false;

        for (int i = 2; i <= MX; i++) {
            if (IS_PRIME[i]) {
                PRIMES.add(i);
                if ((long) i * i <= MX) {
                    for (int j = i * i; j <= MX; j += i) {
                        IS_PRIME[j] = false;
                    }
                }
            }
        }

        S.add(0);
        int t = 0;
        for (int x : PRIMES) {
            t += x;
            if (t > MX) {
                break;
            }
            if (IS_PRIME[t]) {
                S.add(t);
            }
        }
    }

    public int largestPrime(int n) {
        int i = Collections.binarySearch(S, n + 1);
        if (i < 0) {
            i = ~i;
        }
        return S.get(i - 1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static const int MX = 500000;
static vector<bool> IS_PRIME(MX + 1, true);
static vector<int> PRIMES;
static vector<int> S;

auto init = [] {
    IS_PRIME[0] = false;
    IS_PRIME[1] = false;

    for (int i = 2; i <= MX; i++) {
        if (IS_PRIME[i]) {
            PRIMES.push_back(i);
            if (1LL * i * i <= MX) {
                for (int j = i * i; j <= MX; j += i) {
                    IS_PRIME[j] = false;
                }
            }
        }
    }

    S.push_back(0);
    int t = 0;
    for (int x : PRIMES) {
        t += x;
        if (t > MX) break;
        if (IS_PRIME[t]) {
            S.push_back(t);
        }
    }

    return 0;
}();

class Solution {
public:
    int largestPrime(int n) {
        auto it = upper_bound(S.begin(), S.end(), n);
        return *(it - 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const MX = 500000

var (
    isPrime = make([]bool, MX+1)
    primes  []int
    S       []int
)

func init() {
    for i := range isPrime {
        isPrime[i] = true
    }
    isPrime[0] = false
    isPrime[1] = false

    for i := 2; i <= MX; i++ {
        if isPrime[i] {
            primes = append(primes, i)
            if i*i <= MX {
                for j := i * i; j <= MX; j += i {
                    isPrime[j] = false
                }
            }
        }
    }

    S = append(S, 0)
    t := 0
    for _, x := range primes {
        t += x
        if t > MX {
            break
        }
        if isPrime[t] {
            S = append(S, t)
        }
    }
}

func largestPrime(n int) int {
    i := sort.SearchInts(S, n+1)
    return S[i-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const MX = 500000;

const isPrime: boolean[] = Array(MX + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;

const primes: number[] = [];
const s: number[] = [];

(function init() {
    for (let i = 2; i <= MX; i++) {
        if (isPrime[i]) {
            primes.push(i);
            if (i * i <= MX) {
                for (let j = i * i; j <= MX; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    s.push(0);
    let t = 0;
    for (const x of primes) {
        t += x;
        if (t > MX) break;
        if (isPrime[t]) {
            s.push(t);
        }
    }
})();

function largestPrime(n: number): number {
    const i = _.sortedIndex(s, n + 1) - 1;
    return s[i];
}

Comments