【欧拉计划】52. Permuted multiples

(本题取 $n=142857$)

【思路】从 $1$ 开始向更大的数进行枚举,利用 Python 整型字符串自由转换的功能进行判断,找到符合题意的数即可输出。

总体时间复杂度为 $\mathcal O(n)$:

阅读更多

【欧拉计划】51. Prime digit replacements

(本题取 $n=1000000$)

【思路】欧拉筛初始化后,对位数及空缺位置进行枚举,再分别判断 $0 \sim 9$ 填入之后是否为质数即可。

其中,在枚举方面,我们可以在 $0 \sim 9$ 之外新建一个特殊位 $10$,表示这个位置是待替换的。这样,我们的程序就无形之间被简化了。

总体时间复杂度为 $\mathcal O(n)$:

阅读更多

欧拉计划完整版题解

Problem 1: Multiples of 3 and 5

(本题取 $n=1000$)

【思路】$\mathcal O(n)$ 枚举所有能被 $3$ 和被 $5$ 整除的数,最后把能被 $15$ 整除的数减掉:

阅读更多

【欧拉计划】50. Consecutive prime sum

(本题取 $n=1000000$,$m$ 为不超过 $n$ 的质数个数)

【思路】欧拉筛初始化后,采用前缀和预处理,一旦超过 $n$ 就不再继续做下去,这样会减小后续枚举范围。

紧接着在所有质数中枚举作为起始质数,然后取连续的 $maxl+1$ 个质数得到它们的和(规定 $maxl$ 为当前最多质数的个数),再判断是否为质数即可。

总体时间复杂度为 $\mathcal O(n+m^2)$:

阅读更多

【欧拉计划】47. Distinct primes factors

【思路】与 Problem 46 类似,我们先取一个足够大的上限 $n$,先欧拉筛得到质数表和合数表。

在判断合数是否有四个不同的质因数时,我们同样可以采取二分,找到不超过它的最大质数,然后倒着循环,统计出它的不同质因数个数即可。

总体时间复杂度为 $\mathcal O(n \log n)$:

阅读更多

【欧拉计划】46. Goldbach's other conjecture

【思路】取一个足够大的上限 $n$,确保最终答案不超过 $n$。我们可以采用欧拉筛得到所有的质数和合数表。注意合数不是按照顺序得到的,需要排序。

接着我们枚举所有在范围内的合数,二分找到不超过它的最大质数,然后判断二者之差是否能表示乘一个完全平方数的两倍即可。

总体时间复杂度为 $\mathcal O(n \log n)$:

阅读更多

【欧拉计划】44. Pentagon numbers

【思路】选定一个足够大的项数上限 $n$,然后 $\mathcal O(n^2)$ 枚举,判断的时候采用二分,总体时间复杂度为 $\mathcal O(n^2 \log n)$:

阅读更多