Exercise 1 LSE Home MA407

Since the times of the Ancient Greeks, prime numbers have held much fascination for math- ematicians. Although today we know quite a lot about them, many questions remain open and they are still a topic under intensive study. (For example, only in 2004 it was proved by Green and Tao that the primes contain arbitrarily long arithmetic progressions.)

In the following two exercises we look at computational aspects of the primes. This topic is important, for example because prime numbers play an important role in cryptography. In fact, it has also seen relatively recent breakthroughs: In 2002 Agrawal, Kayal and Saxena developed a particularly efficient algorithm that reliably tests whether a number is prime.

Such advanced algorithms are beyond what we will cover in this exercise and course (it needs a fair amount of mathematics to understand their approach). But how can one generate prime numbers? How can one test whether a number is prime? It is your task to answer these questions (through simple algorithms).

Exercise 1.1

(a) Describe (in words or pseudocode) an algorithm to determine for a given integer n the next prime number p after or equal to n, that is, the prime number p ≥ n such that p − n is minimised.

(b) Argue that your algorithm is correct.

(c) Very roughly, estimate how efficient your algorithm is: That is, look at the loops used in your algorithm and estimate roughly how many iterations in each loop your algorithm needs for a given number n.

Solution 1

Parts (b) and (c) of the exercise above are demanding at this point, because we did not yet cover this kind of analysis of algorithms in the course (but will do so very shortly). Nevertheless, it is hopefully obvious that these are important questions when designing an algorithm. So see what you can do for now.

Submit this part of this exercise sheet in the Gradescope assignment “Exercise 1.1,” where you can type your answer as text. (You might first want to prepare your answers by writing them down in a file in plain text; you can then paste your answers into Gradescope.)

The next exercise asks you to turn your algorithm into a Python program.

Exercise 1.2

Write a Python function primeAtLeast(n) in a file called Primes.py that expects one argument (the number n from above) and implements your algorithm (thus, returns the next prime after n).

Do not forget to test your program with some small and some large numbers, to see whether it works correctly. (It is easy to find primes tables on the internet.) If your program has some flaw and you cannot fix this, then note this in a comment in your file.

Submit your Python file on Gradescope, under the assignment “Exercise 1.2 (PrimeAtLeast)”.

Solution 2

# Primes.py

def primeAtLeast(n):
    def is_prime(num):
        """Check if a number is prime."""
        if num < 2:
            return False
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

    # 如果 n 小于 2，直接返回 2
    if n < 2:
        return 2

    # 如果 n 是偶数，加 1 使其变为奇数
    if n % 2 == 0:
        n += 1

    # 检查 n 是否是质数，如果不是，则加 2 并继续检查
    while not is_prime(n):
        n += 2

    return n

# 用于测试的代码
if __name__ == "__main__":
    test_nums = [1, 2, 3, 15, 20, 100, 1000, 10000]
    for num in test_nums:
        print(f"The prime number at least {num} is: {primeAtLeast(num)}")

# 注：此代码适用于小到中等大小的 n。对于非常大的 n，可能需要更高效的算法。

补充

Q1 为什么：i * i <= n？

使用 i * i <= n 作为循环条件是基于数学上的一个性质和计算上的一个优化。

1. 数学性质：如果一个数 ( n ) 不是素数，那么它必然可以表示为两个因子的乘积，即 ( $n = a \times b$ )。而这两个因子，如果它们都大于 ( $\sqrt{n}$ )，那么它们的乘积 ( $a \times b$ ) 就会大于 ( n )，这与前提是矛盾的。反之，如果它们都小于 ( $\sqrt{n}$ )，那么它们的乘积 ( $a \times b$ ) 也会小于 ( n )。因此，对于 ( $n = a \times b$ ) 这样的分解，其中一个因子必然小于或等于 ( $\sqrt{n}$ )，而另一个因子必然大于或等于 ( $\sqrt{n}$ )。

2. 计算优化：由上述性质，我们知道，只需检查到 ( $\sqrt{n}$ ) 就足够了。如果 ( n ) 在 2 到 ( $\sqrt{n}$ ) 之间没有因子，那么 ( n ) 在 ( $\sqrt{n}$ ) 到 ( n ) 之间也不会有因子。因此，我们可以大大减少需要检查的因子的数量，从而提高算法的效率。

基于这两点，我们通常在检查素数时使用 i * i <= n 作为循环条件，这样可以在效率上得到优化，同时也确保了正确性。

Q2

1. 返回值问题：当 n == 2 时，你的代码返回了 2。但是，is_prime 函数应当返回布尔值（True 或 False），而不是数字，以表示输入的数是否为素数。所以，应当返回 True 而不是 2。

2. 循环条件问题：你的 while 循环条件 while i>1 仍然是错误的。这意味着循环条件总是成立，但由于循环内部你有两个返回语句，所以它不会进入无限循环。但是这个循环条件本身是没有意义的。你应该设置循环条件为 while i * i <= n。

3. 循环逻辑问题：你的循环内部的逻辑是：只要 n 不被 i 整除，就返回 n。但是这不是检查一个数是否为素数的正确逻辑。正确的逻辑应当是：只要 n 能被 2 到 $\sqrt{(n)}$ 之间的任何数整除，那么 n 就不是素数。如果在循环结束后仍然没有找到一个可以整除 n 的数，那么 n 就是素数。

4. 循环内未更新 i：你需要在循环的结尾更新 i 的值，否则它会永远检查相同的 i 值。

以下是修复后的代码：

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

使用这个修复后的函数，你可以正确地检查一个数是否为素数。

公众号：AI悦创【二维码】