Project Euler 347

题目

Largest integer divisible by two primes

The largest integer $\le 100$ that is only divisible by both the primes $2$ and $3$ is $96$, as $96=323=2^53$.

For two distinct primes $p$ and $q$ let $M(p,q,N)$ be the largest positive integer $\le N$ only divisible by both $p$ and $q$ and $M(p,q,N)=0$ if such a positive integer does not exist.

E.g. $M(2,3,100)=96$.

$M(3,5,100)=75$ and not $90$ because $90$ is divisible by $2 ,3$ and $5$.

Also $M(2,73,100)=0$ because there does not exist a positive integer $\le 100$ that is divisible by both $2$ and $73$.

Let $S(N)$ be the sum of all distinct $M(p,q,N)$.
$S(100)=2262.$

Find $S(10 000 000)$.

解决方案

根据分解质因数的思想可以知道，如果$p,q$有其中一个不相同，那么$M(p,q,N)$也不会相同。

因此，令$N=10000000$，枚举所有的$p,q(p< q)$使得$pq\le N$。那么找到一对$(x,y)$使得$p^xq^y\le N$并且$p^xq^y$最大，那么$p^xq^y$便是其中一个答案。

另外一个地方则是，质数只需要筛选到$\dfrac{N}{2}$即可。因为枚举的$(p,q)$中，$p$至少为$2$，那么$q$最多为$\dfrac{N}{2}$。

代码

from tools import get_prime

N = 10 ** 7
pr = get_prime(N // 2)
ans = 0
for i in range(len(pr) - 1):
    for j in range(i + 1, len(pr)):
        if pr[i] * pr[j] > N:
            break
        mx = 0
        x = pr[i]
        while x * pr[j] <= N:
            y = pr[j]
            while x * y <= N:
                mx = max(mx, x * y)
                y *= pr[j]
            x *= pr[i]
        ans += mx
print(ans)