找到第 10001 个素数 - 如何优化? [英] Finding the 10001st prime - how to optimize?

问题描述

Project Euler 问题 7 说:

Project Euler problem 7 says:

通过列出前六个素数:2、3、5、7、11和13，我们可以看到第 6 个素数是 13.第 10001 个素数是多少?

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?

这是我用 Python 编写的代码:

Here's the code I've written in Python:

def primes(n):
    primes = []
    attempt = 3
    while len(primes) < (n-1):
        for i in range(len(primes)):
            if attempt % primes[i] == 0:
                attempt += 2
                break
        else:
            primes.append(attempt)
            print (primes)
    return (primes)

在测试一个数字时，如果发现该数字可以被列表中的一个素数整除，for 循环就会中断，并从一个更大的数字重新开始.如果它不可整除，则将其添加到素数列表中.这一直持续到列表达到所需的大小(在本例中为 10000，我省略了 2，因此列表的最后一个成员是第 10001 个素数)

While testing a number, if it finds that the number is divisible by one of the primes in the list, the for loop breaks, and starts again with a larger number. If it isn't divisible, it's added to the list of primes. This keeps going until the list is as large as desired (in this case 10000, and I've omitted 2 so the last member of the list is the 10001st prime)

问题是这非常慢.我已经看到其他解决方案显然可以解决这个问题，如果不是更少的话.有什么方法可以让这件事变得更有趣?

The problem is that this is extremely SLOW. I've seen other solutions that can apparently solve this is seconds, if not less. What are some ways I could make this fun faster?

推荐答案

这些是优化问题，因此您不希望每次更新列表时都打印.另一件事是根本不要使用列表，因为它的内存效率不是很高.您应该改用生成器.它非常快，您不会使用列表消耗内存.下面是用于此目的的代码，观察如何使用 yield 关键字将 count_primes 函数转换为生成器.

These are optimizations problems, so you don't want to be printing every time you update the list. The other thing is don't use list at all because is not very memory efficient. You should use instead generators. Its very fast and you don't get to consume memory using lists. Below is a code for this purpose, watch how the yield keyword is being used in order to convert count_primes function into a generator.

def is_prime(num):
    """
    Checks if a number is prime
    """
    prime_counter = 1
    for x in range(1, num):
        if num % x == 0:
            prime_counter += 1
        if prime_counter > 2:
            return False
    return True


def count_primes():
    """
    Counts primes until PRIMES_TO_COUNT
    is reached
    """
    PRIMES_TO_COUNT = 1000       # Modify this value
    prime_counter_num = 0
    start_point_num = 1
    while True:
        if is_prime(start_point_num):
            if prime_counter_num == PRIMES_TO_COUNT:
                yield start_point_num
                print "This is the %dth prime number: %s" \
                      % (prime_counter_num, start_point_num)
                break
            prime_counter_num += 1
        start_point_num += 1


if __name__ == '__main__':
    for prime_number in count_primes():
        print prime_number

希望对你有帮助！Python 生成器！

这篇关于找到第 10001 个素数 - 如何优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！