Sum of Exclusive Prime Multiples
In financial systems, analyzing numbers based on their divisibility properties is a common task, crucial for areas like transaction categorization, fraud detection, or specialized reporting. This problem explores a specific divisibility pattern: identifying and summing numbers whose prime factors are exclusively from a given set of 'special' primes.
Given an integer N and a list of distinct prime numbers primes, your task is to find the sum of all positive integers x such that 1 <= x <= N and x is divisible by exactly one prime from the primes list.
N: An integer representing the upper bound (inclusive) for numbers to consider.primes: An array of distinct prime numbers.x satisfying the condition.primes array will only contain distinct prime numbers.N can be a large number, so an efficient solution is required.1 to N, return 0.Examples
Example 1
Input:
N = 10, primes = [2, 3]
Output:
36
Note:
Numbers up to 10:
Example 2
Input:
N = 20, primes = [2, 5]
Output:
100
Note:
Numbers up to 20 divisible by exactly one of [2, 5]:
Example 3
Input:
N = 100, primes = [7, 11, 13]
Output:
1594
Note:
For N=100, the products of any two distinct primes from [7, 11, 13] (e.g., 711=77, 713=91, 11*13=143) are either greater than N or have only one multiple within N (e.g., 77, 91). Products of three primes are always > N.
Constraints
1 <= N <= 10^81 <= primes.length <= 102 <= primes[i] <= 1000primes are distinct prime numbers.number type).primes are indeed prime or distinct. Assume input validity.N or elements in primes.N and primes.length efficiently, avoiding brute-force iteration where unnecessary.primes list or N being too small to contain any valid multiples.Loading editor...