将所有数字分解为给定数字的快速算法

Question

我正在寻找一种算法，可以根据已经分解的数字分解数字。换句话说，我正在寻找一种快速算法来将所有数字分解为给定数字，并将它们存储在（我想这是最容易使用的数据结构）列表/元组元组中。我正在寻找一种“最多 n”的算法，因为我需要最多“n”的所有数字，而且我想这比一个一个地检查要快。

对于我正在运行的程序，我希望此算法在合理的时间内（不到一小时）运行 2*10^8。我在 python 中尝试了一种更天真的方法，首先找到“n”之前的所有素数，然后对于每个数字“k”，通过检查每个素数直到被除以它（我们称之为 p），找到它的素因数分解，那么它的因式分解就是 k/p + p 的因式分解。

from math import *

max=1000000 # We will check all numbers up to this number, 

lst = [True] * (max - 2) # This is an algorithm I found online that will make the "PRIMES" list all the primes up to "max", very efficent

for i in range(2, int(sqrt(max) + 1)):

  if lst[i - 2]:

    for j in range(i ** 2, max, i):

      lst[j - 2] = False

PRIMES = tuple([m + 2 for m in range(len(lst)) if lst[m]]) # (all primes up to "max")

FACTORS = [(0,),(1,)] #This will be a list of tuples where FACTORS[i] = the prime factors of i

for c in range(2,max): #check all numbers until max

  if c in PRIMES:

    FACTORS.append((c,)) #If it's a prime just add it in

  else: #if it's not a prime...

    i=0

    while PRIMES[i]<= c: #Run through all primes until you find one that divides it,

      if c%PRIMES[i] ==0: 

        FACTORS.append(FACTORS[c//PRIMES[i]] + (PRIMES[i],)) #If it does, add the prime with the factors of the division

        break

      i+=1

从测试来看，绝大多数时间都浪费在检查候选人是否为素数之后的 else 部分。这需要的不仅仅是我们的 for max = 200000000

Answer 1

您可以使用脚本的第一部分来做到这一点！代码：from math import *import timeMAX = 40000000t = time.time()# factors[i] = all the prime factors of ifactors = {}# Running over all the numbers smaller than sqrt(MAX) since they can be the factors of MAXfor i in range(2, int(sqrt(MAX) + 1)):&nbsp; &nbsp; # If this number has already been factored - it is not prime&nbsp; &nbsp; if i not in factors:&nbsp; &nbsp; &nbsp; &nbsp; # Find all the future numbers that this number will factor&nbsp; &nbsp; &nbsp; &nbsp; for j in range(i * 2, MAX, i):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if j not in factors:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; factors[j] = [i]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; factors[j].append(i)print(time.time() - t)for i in range(3, 15):&nbsp; &nbsp; if i not in factors:&nbsp; &nbsp; &nbsp; &nbsp; print(f"{i} is prime")&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; print(f"{i}: {factors[i]}")结果：3: 是质数4: [2]5: 是质数6: [2, 3]7: 是质数8: [2]9: [3]10: [2, 5]11: 是质数12: [2, 3]13: 是质数14: [2, 7]解释：正如评论中提到的，它是对埃拉托色尼筛法算法的修改。对于每个数字，我们找到它可以在未来因式分解的所有数字。如果该数字未出现在结果字典中，则它是素数，因为没有数字将其分解。我们使用字典而不是列表，因此根本不需要保存质数——这对内存更友好但也有点慢。时间：根据MAX = 40000000with time.time(): 110.14351892471313seconds 的简单检查。对于MAX = 1000000：1.0785243511199951秒。对于MAX = 200000000with time.time()：1.5 小时后未完成...它已达到主循环中 6325 项中的第 111 项（这还不错，因为循环越远，它们变得越短）。然而，我确实相信一个写得很好的 C 代码可以在半小时内完成（如果你愿意考虑它，我可能会写另一个答案）。可以做的更多优化是使用多线程和一些像 Miller–Rabin 这样的素数测试。当然值得一提的是，这些结果是在我的笔记本电脑上得出的，也许在 PC 或专用机器上它会运行得更快或更慢。

Answer 2

编辑：我实际上在代码审查中问了一个关于这个答案的问题，它有一些关于运行时的很酷的图表！编辑#2：有人回答了我的问题，现在代码经过一些修改可以在 2.5 秒内运行。由于之前的答案写在里面，Python所以速度很慢。下面的代码做的是完全相同的，但在 中C++，它有一个线程每 10 秒监控一次它获得了哪个素数。#include <math.h>#include <unistd.h>#include <list>#include <vector>#include <ctime>#include <thread>#include <iostream>#include <atomic>#ifndef MAX#define MAX 200000000#define TIME 10#endifstd::atomic<bool> exit_thread_flag{false};void timer(int *i_ptr) {&nbsp; &nbsp; for (int i = 1; !exit_thread_flag; i++) {&nbsp; &nbsp; &nbsp; &nbsp; sleep(TIME);&nbsp; &nbsp; &nbsp; &nbsp; if (exit_thread_flag) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; std::cout << "i = " << *i_ptr << std::endl;&nbsp; &nbsp; &nbsp; &nbsp; std::cout << "Time elapsed since start: "&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; << i * TIME&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; << " Seconds" << std::endl;&nbsp; &nbsp; }}int main(int argc, char const *argv[]){&nbsp; &nbsp; int i, upper_bound, j;&nbsp; &nbsp; std::time_t start_time;&nbsp; &nbsp; std::thread timer_thread;&nbsp; &nbsp; std::vector< std::list< int > > factors;&nbsp; &nbsp; std::cout << "Initiallizating" << std::endl;&nbsp; &nbsp; start_time = std::time(nullptr);&nbsp; &nbsp; timer_thread = std::thread(timer, &i);&nbsp; &nbsp; factors.resize(MAX);&nbsp; &nbsp; std::cout << "Initiallization took "&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; << std::time(nullptr) - start_time&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; << " Seconds" << std::endl;&nbsp; &nbsp; std::cout << "Starting calculation" << std::endl;&nbsp; &nbsp; start_time = std::time(nullptr);&nbsp; &nbsp; upper_bound = sqrt(MAX) + 1;&nbsp; &nbsp; for (i = 2; i < upper_bound; ++i)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if (factors[i].empty())&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (j = i * 2; j < MAX; j += i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; factors[j].push_back(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; std::cout << "Calculation took "&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; << std::time(nullptr) - start_time&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; << " Seconds" << std::endl;&nbsp; &nbsp; // Closing timer thread&nbsp; &nbsp; exit_thread_flag = true;&nbsp; &nbsp; std::cout << "Validating results" << std::endl;&nbsp; &nbsp; for (i = 2; i < 20; ++i)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; std::cout << i << ": ";&nbsp; &nbsp; &nbsp; &nbsp; if (factors[i].empty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::cout << "Is prime";&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int v : factors[i]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::cout << v << ", ";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; std::cout << std::endl;&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; timer_thread.join();&nbsp; &nbsp; return 0;}它需要用以下行编译：g++ main.cpp -std=c++0x -pthread如果您不想将整个代码转换为 C++，您可以使用 Python 中的子进程库。时间：好吧，我尽了最大努力，但它仍然运行了一个多小时……它6619在 1.386111 小时（4990 秒）内达到了第 855 个素数（好多了！）。所以这是一个进步，但还有一段路要走！（没有另一个线程可能会更快）