为了提供一个具体的例子,我们需要编写代码来验证一个数字是否是质数。现在有很多算法,例如:可以用埃拉托色尼的筛子(sieve of Eratosthenes)来分离质数和非质数。如果有很多验证数字,我们不希望对每一个数字都进行Eratosthenes筛选。我们想要做的是将所有质数一次制表,直到数字的上限,然后使用一个表查的方式,找来验证大量的数字。
"""Generates C++ vector of prime numbers up to max_numberusing sieve of Eratosthenes."""import pathlibimport sys# for simplicity we do not verify argument listmax_number =int(sys.argv[-2])output_file_name = pathlib.Path(sys.argv[-1])numbers =range(2, max_number +1)is_prime ={number:Truefor number in numbers}for number in numbers: current_position = numberif is_prime[current_position]:while current_position <= max_number: current_position += number is_prime[current_position]=Falseprimes = (number for number in numbers if is_prime[number])code ="""#pragma once#include <vector>const std::size_t max_number = {max_number};std::vector<int> & primes() {{ static std::vector<int> primes;{push_back} return primes;}}"""push_back ='\n'.join([' primes.push_back({:d});'.format(x) for x in primes])output_file_name.write_text(code.format(max_number=max_number, push_back=push_back))
我们的目标是生成一个primes.hpp,并将其包含在下面的示例代码中:
#include"primes.hpp"#include<iostream>#include<vector>intmain() { std::cout <<"all prime numbers up to "<< max_number <<":";for (auto prime :primes()) std::cout <<" "<< prime; std::cout << std::endl;return0;}