第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全，請及時綁定郵箱和手機(jī)立即綁定
已解決430363個問題，去搜搜看，總會有你想問的

將所有數(shù)字分解為給定數(shù)字的快速算法

將所有數(shù)字分解為給定數(shù)字的快速算法

慕工程0101907 2023-02-15 16:42:22
我正在尋找一種算法，可以根據(jù)已經(jīng)分解的數(shù)字分解數(shù)字。換句話說，我正在尋找一種快速算法來將所有數(shù)字分解為給定數(shù)字，并將它們存儲在（我想這是最容易使用的數(shù)據(jù)結(jié)構(gòu)）列表/元組元組中。我正在尋找一種“最多 n”的算法，因為我需要最多“n”的所有數(shù)字，而且我想這比一個一個地檢查要快。對于我正在運行的程序，我希望此算法在合理的時間內(nèi)（不到一小時）運行 2*10^8。我在 python 中嘗試了一種更天真的方法，首先找到“n”之前的所有素數(shù)，然后對于每個數(shù)字“k”，通過檢查每個素數(shù)直到被除以它（我們稱之為 p），找到它的素因數(shù)分解，那么它的因式分解就是 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 efficentfor i in range(2, int(sqrt(max) + 1)):  if lst[i - 2]:    for j in range(i ** 2, max, i):      lst[j - 2] = FalsePRIMES = 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 ifor 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從測試來看，絕大多數(shù)時間都浪費在檢查候選人是否為素數(shù)之后的 else 部分。這需要的不僅僅是我們的 for max = 200000000
查看完整描述

2 回答

?
函數(shù)式編程

TA貢獻(xiàn)1807條經(jīng)驗 獲得超9個贊

您可以使用腳本的第一部分來做到這一點！


代碼：


from math import *

import time


MAX = 40000000


t = time.time()

# factors[i] = all the prime factors of i

factors = {}

# Running over all the numbers smaller than sqrt(MAX) since they can be the factors of MAX

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

    # If this number has already been factored - it is not prime

    if i not in factors:

        # Find all the future numbers that this number will factor

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

            if j not in factors:

                factors[j] = [i]

            else:

                factors[j].append(i)

print(time.time() - t)


for i in range(3, 15):

    if i not in factors:

        print(f"{i} is prime")

    else:

        print(f"{i}: {factors[i]}")

結(jié)果：


3: 是質(zhì)數(shù)

4: [2]

5: 是質(zhì)數(shù)

6: [2, 3]

7: 是質(zhì)數(shù)

8: [2]

9: [3]

10: [2, 5]

11: 是質(zhì)數(shù)

12: [2, 3]

13: 是質(zhì)數(shù)

14: [2, 7]


解釋：


正如評論中提到的，它是對埃拉托色尼篩法算法的修改。

對于每個數(shù)字，我們找到它可以在未來因式分解的所有數(shù)字。

如果該數(shù)字未出現(xiàn)在結(jié)果字典中，則它是素數(shù)，因為沒有數(shù)字將其分解。我們使用字典而不是列表，因此根本不需要保存質(zhì)數(shù)——這對內(nèi)存更友好但也有點慢。


時間：


根據(jù)MAX = 40000000with time.time(): 110.14351892471313seconds 的簡單檢查。

對于MAX = 1000000：1.0785243511199951秒。

對于MAX = 200000000with time.time()：1.5 小時后未完成...它已達(dá)到主循環(huán)中 6325 項中的第 111 項（這還不錯，因為循環(huán)越遠(yuǎn)，它們變得越短）。


然而，我確實相信一個寫得很好的 C 代碼可以在半小時內(nèi)完成（如果你愿意考慮它，我可能會寫另一個答案）?？梢宰龅母鄡?yōu)化是使用多線程和一些像 Miller–Rabin 這樣的素數(shù)測試。當(dāng)然值得一提的是，這些結(jié)果是在我的筆記本電腦上得出的，也許在 PC 或?qū)Ｓ脵C(jī)器上它會運行得更快或更慢。


查看完整回答
反對 回復(fù) 2023-02-15
?
紅顏莎娜

TA貢獻(xiàn)1842條經(jīng)驗 獲得超13個贊

編輯：


我實際上在代碼審查中問了一個關(guān)于這個答案的問題，它有一些關(guān)于運行時的很酷的圖表！


編輯#2：


有人回答了我的問題，現(xiàn)在代碼經(jīng)過一些修改可以在 2.5 秒內(nèi)運行。


由于之前的答案寫在里面，Python所以速度很慢。下面的代碼做的是完全相同的，但在 中C++，它有一個線程每 10 秒監(jiān)控一次它獲得了哪個素數(shù)。


#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

#endif



std::atomic<bool> exit_thread_flag{false};


void timer(int *i_ptr) {

    for (int i = 1; !exit_thread_flag; i++) {

        sleep(TIME);

        if (exit_thread_flag) {

            break;

        }

        std::cout << "i = " << *i_ptr << std::endl;

        std::cout << "Time elapsed since start: " 

                  << i * TIME 

                  << " Seconds" << std::endl;

    }

}


int main(int argc, char const *argv[])

{

    int i, upper_bound, j;

    std::time_t start_time;

    std::thread timer_thread;

    std::vector< std::list< int > > factors;


    std::cout << "Initiallizating" << std::endl;

    start_time = std::time(nullptr);

    timer_thread = std::thread(timer, &i);

    factors.resize(MAX);

    std::cout << "Initiallization took " 

              << std::time(nullptr) - start_time 

              << " Seconds" << std::endl;


    std::cout << "Starting calculation" << std::endl;

    start_time = std::time(nullptr);

    upper_bound = sqrt(MAX) + 1;

    for (i = 2; i < upper_bound; ++i)

    {

        if (factors[i].empty())

        {

            for (j = i * 2; j < MAX; j += i)

            {

                factors[j].push_back(i);

            }

        }

    }

    std::cout << "Calculation took " 

              << std::time(nullptr) - start_time 

              << " Seconds" << std::endl;


    // Closing timer thread

    exit_thread_flag = true;


    std::cout << "Validating results" << std::endl;

    for (i = 2; i < 20; ++i)

    {

        std::cout << i << ": ";

        if (factors[i].empty()) {

            std::cout << "Is prime";

        } else {

            for (int v : factors[i]) {

                std::cout << v << ", ";

            }

        }

        std::cout << std::endl;

    }

    

    timer_thread.join();

    return 0;

}

它需要用以下行編譯：


g++ main.cpp -std=c++0x -pthread

如果您不想將整個代碼轉(zhuǎn)換為 C++，您可以使用 Python 中的子進(jìn)程庫。


時間：


好吧，我盡了最大努力，但它仍然運行了一個多小時……它6619在 1.386111 小時（4990 秒）內(nèi)達(dá)到了第 855 個素數(shù)（好多了?。Ｋ赃@是一個進(jìn)步，但還有一段路要走?。]有另一個線程可能會更快）


查看完整回答
反對 回復(fù) 2023-02-15
  • 2 回答
  • 0 關(guān)注
  • 159 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

 公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號