4079. Prime Subset Selection I

DifficultyMedium

Description

You are given two integers n and s.

Consider all prime numbers less than or equal to n. Select some of these primes such that:

The sum of the selected primes is less than or equal to s.
The number of selected primes is maximized.
Each prime can be selected at most once.

Return an integer array containing the selected primes in increasing order. If multiple optimal selections exist, return any of them.

If no prime can be selected, return an empty array.

Example 1:

Input: n = 7, s = 20

Output: [2,3,5,7]

Explanation:

The prime numbers less than or equal to n = 7 are 2, 3, 5, and 7.
The sum of all these primes is 2 + 3 + 5 + 7 = 17, which is less than or equal to s = 20.
Thus, the answer is [2, 3, 5, 7].

Example 2:

Input: n = 15, s = 15

Output: [3,5,7]

Explanation:

The prime numbers less than or equal to n = 15 are 2, 3, 5, 7, 11, and 13.
One possible selection is [3, 5, 7], whose sum is 3 + 5 + 7 = 15.
The four smallest available primes have sum 2 + 3 + 5 + 7 = 17, which exceeds s = 15. Therefore, selecting four or more primes is impossible, and the maximum number of selected primes is three.
Thus, [3, 5, 7] is one possible answer. Other valid answers include [2, 3, 5], [2, 3, 7], and [2, 5, 7].

Example 3:

Input: n = 5, s = 1

Output: []

Explanation:

The smallest prime number is 2, which is greater than s = 1.
Thus, no prime can be selected, so the answer is an empty array.

Constraints:

1 <= n <= 10⁶
1 <= s <= 10⁹

Solutions

Solution 1: Sieve and Greedy Selection

Thinking

The goal is to take as many primes as possible without letting their sum exceed \(s\). With \(n\) up to \(10^6\) and \(s\) up to \(10^9\), a knapsack over subsets does not fit.

Among all subsets of a fixed size, the smallest sum comes from the smallest primes. The largest feasible size is therefore the longest prefix of the primes in increasing order whose sum is still at most \(s\).

Sieve the primes up to \(10^6\) first. A query then takes them in order until the next prime is larger than \(n\) or larger than the remaining budget.

Use the sieve of Eratosthenes to precompute every prime up to \(10^6\) and store the primes in increasing order. For a query \((n,s)\), scan that list from small to large. Stop when the current prime \(p\) is greater than \(n\) or greater than the remaining budget \(s\); otherwise append \(p\) to the answer and subtract \(p\) from \(s\).

The selected primes are the smallest ones that do not exceed \(n\). They have the minimum sum among all subsets of the same size, so the size is already maximum. Any optimal subset is acceptable.

The sieve takes \(O(M\log\log M)\) time and \(O(M)\) space, where \(M=10^6\). Each query takes \(O(\pi(n))\) time, where \(\pi(n)\) is the number of primes not exceeding \(n\).

Python3JavaC++GoTypeScript

mx = 10**6
primes = []
is_prime = [True] * (mx + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, mx + 1):
    if is_prime[i]:
        primes.append(i)
        if i * i <= mx:
            for j in range(i * i, mx + 1, i):
                is_prime[j] = False


class Solution:
    def maxPrimes(self, n: int, s: int) -> list[int]:
        ans = []
        for p in primes:
            if p > n or p > s:
                break
            ans.append(p)
            s -= p
        return ans

class Solution {
    static int mx = 1000000;
    static List<Integer> primes = new ArrayList<>();

    static {
        boolean[] isPrime = new boolean[mx + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i <= mx; i++) {
            if (isPrime[i]) {
                primes.add(i);
                if (i <= mx / i) {
                    for (int j = i * i; j <= mx; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
        }
    }

    public List<Integer> maxPrimes(int n, int s) {
        List<Integer> ans = new ArrayList<>();
        for (int p : primes) {
            if (p > n || p > s) {
                break;
            }
            ans.add(p);
            s -= p;
        }
        return ans;
    }
}

class Solution {
    static const int mx = 1000000;
    static vector<int> primes;

public:
    vector<int> maxPrimes(int n, int s) {
        vector<int> ans;
        for (int p : primes) {
            if (p > n || p > s) {
                break;
            }
            ans.push_back(p);
            s -= p;
        }
        return ans;
    }
};

const int Solution::mx;
vector<int> Solution::primes = [] {
    vector<bool> isPrime(mx + 1, true);
    isPrime[0] = isPrime[1] = false;
    vector<int> primes;

    for (int i = 2; i <= mx; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            if (i <= mx / i) {
                for (int j = i * i; j <= mx; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
    return primes;
}();

const mx = 1000000

var primes = func() []int {
    isPrime := make([]bool, mx+1)
    for i := 2; i <= mx; i++ {
        isPrime[i] = true
    }

    primes := make([]int, 0)
    for i := 2; i <= mx; i++ {
        if isPrime[i] {
            primes = append(primes, i)
            if i <= mx/i {
                for j := i * i; j <= mx; j += i {
                    isPrime[j] = false
                }
            }
        }
    }
    return primes
}()

func maxPrimes(n int, s int) []int {
    ans := make([]int, 0)
    for _, p := range primes {
        if p > n || p > s {
            break
        }
        ans = append(ans, p)
        s -= p
    }
    return ans
}

const mx = 10 ** 6;

const primes: number[] = (() => {
    const isPrime = new Uint8Array(mx + 1).fill(1);
    isPrime[0] = isPrime[1] = 0;
    const primes: number[] = [];

    for (let i = 2; i <= mx; i++) {
        if (isPrime[i]) {
            primes.push(i);
            if (i <= mx / i) {
                for (let j = i * i; j <= mx; j += i) {
                    isPrime[j] = 0;
                }
            }
        }
    }
    return primes;
})();

function maxPrimes(n: number, s: number): number[] {
    const ans: number[] = [];
    for (const p of primes) {
        if (p > n || p > s) {
            break;
        }
        ans.push(p);
        s -= p;
    }
    return ans;
}

4079. Prime Subset Selection I

Description

Solutions

Solution 1: Sieve and Greedy Selection

Comments