我遇到了一个问题,题目要求给定一个数字N
和一组数字S = {s1,s2,.....sn}
,其中s1 < s2 < sn < N
,从范围1..N
中删除所有{s1, s2,....sn}
的倍数。
示例:
Let N = 10
S = {2,4,5}
Output: {1, 7, 9}
Explanation: multiples of 2 within range: 2, 4, 6, 8
multiples of 4 within range: 4, 8
multiples of 5 within range: 5, 10
我希望采用算法方法,提供伪代码而非完整解决方案。 我尝试过的:
(Considering the same example as above)
1. For the given N, find all the prime factors of that number.
Therefore, for 10, prime-factors are: 2,3,5,7
In the given set, S = {2,4,5}, the prime-factors missing from
{2,3,5,7} are {3,7}.
2. First, check prime-factors that are present: {2,5}
Hence, all the multiples of them will be removed
{2,4,5,6,8,10}
3. Check for non-prime numbers in S = {4}
4. Check, if any divisor of these numbers has already been
previously processed.
> In this case, 2 is already processed.
> Hence no need to process 4, as all the multiples of 4
would have been implicitly checked by the previous
divisor.
If not,
> Remove all the multiples from this range.
5. Repeat for all the remaining non primes in the set.
请提出您的想法!