欧拉计划刷题记录——1

Problem 7 10001st prime

By listing the first six prime numbers:2,3,5,7,11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

此处使用欧拉筛法寻找质数

m = 1000000 #数组长度限制
n = 10001 #取第n位质数
x = 2  #提前定义的倍数值
c = 0  #质数的计数
prime = [True for i in range(0, m)]
for i in range(2, m):
    if prime[i]:
        while i*x < m:
            prime[i*x] = False
            x += 1
        x = 2
        c += 1
    if c == n:   #发现答案就退出计算
        print(i)
        break

---

Problem 9 Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which,
$$a^2 + b^2 = c^2$$
For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

There exists exactly one Pythagorean triplet for which $$a + b + c = 1000$$ . Find the product .

此处直接暴力枚举

n = 1000
for j in range(1, n//2):
    for i in range(1, j):
        k = n - i - j
        if (i**2 + j**2 == k**2):
            print((i,j,k))

---

Problem 10 Summation of primes

The sum of the primes below 10 is $2 + 3 + 5 + 7 = 170$.

Find the sum of all the primes below two million.

同样是使用欧拉筛找质数，再求和

m = 2000000 #最大值限制
x = 2  #提前定义的倍数值
prime = [True for i in range(0, m)]
for i in range(2, m):
    if prime[i]:
        while i*x < m:
            prime[i*x] = False
            x += 1
        x = 2
        
print(sum([i for i in range(2, m) if prime[i]])) #求和

---

Problem 12 Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the th triangle number would be $$1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 $$. The first ten terms would be:
$$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots$$

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

约数定理

def factor(x):  #用约数定理快速求约数个数
    ans = 1
    while x != 1:
        i = 2
        a = 1
        while x % i != 0:
            i += 1
        while x % i == 0:
            x = x // i
            a += 1
        ans *= a
    return ans


m = 100000 #范围限制
n = 500  #约数数的限制
for i in range(1, m):
    j = i*(i+1)//2
    if factor(j) > n:
        print(j)
        break

---

Problem 14 Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

$$n \rightarrow n/2( is . even) , n \rightarrow 3n+1( is . odd)$$

Using the rule above and starting with 13, we generate the following sequence:
13,40,20,10,5,16,8,4,2,1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at .

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

使用字典储存多次出现的结果

collatz = {}  #储存已知结果

def cillatz_length(x):  #计算长度
    if x == 1: return 1
    if collatz.get(x) != None: return collatz[x]
    a = 1
    if x % 2 == 0:
        a = x // 2
    else:
        a = 3 * x + 1
    collatz[x] = cillatz_length(a) + 1   #递归运算并存储长度
    return collatz[x]

n = 1000000  #数量限制
ans = 1
ans_l = 1
for i in range(1, n):
    if cillatz_length(i) > ans_l:
        ans = i
        ans_l = collatz[i]
print((ans, ans_l))  #输出结果

---

Problem 15 Lattice paths

Starting in the top left corner of a $2 \times 2$ grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a $20 \times 20$ grid?

此题相当于在问 20*20次行动中选二十次向下走，其他情况向右走，问有多少种选法。
如此，答案便不难得到 $C_{40}^{20}$

打赏