找出一個數字的因子

Question

找出一個數字的除數的最優化方法是什麼，這樣除數至少有數字3？

例如21 = 1,3,7,21

因此只有一個除數的數字爲3。

例如因此 62 = 1,2,31,62

只有一個除數中有數字3和Ie 31

EDIT-i的意識到，要做到這一點的最佳方式woulds是找出所有因素

Getting Factors of a Number

What is the best way to get all the divisors of a number?

0123：一個號碼，檢查包含數字3

找出因素的最佳途徑因素

Answer 1

這是我的一個擴展。它首先檢查列表div3中是否有可能的因子。如果不是，它會添加最多號碼/2的候選人，根據此列表跳過已經可以考慮的值，因此會添加「37」和「43」，但不會添加「36」或「39」。

以上部分應視爲「設置」。如果知道輸入約束（最大輸入值），則可以計算一次向量div3，然後將其存儲在程序中。

如果列表div3是最新的，則應將輸入分解爲其中一個數字。如果它不能，那麼它的所有因素都不包含'3'。如果它可以可以，這表示剩餘部分，可以使用常規方法進一步考慮其餘部分。

我認爲這是「優化的」，因爲約束「任何因子應該包含'3'」首先被檢查。只有找到任何有效因子，您才需要計算所有其他因子。

使用<vector>及其同類我的第一個項目，所以，請溫柔在您的意見:-)

（編輯）我現在注意到的因素檢查循環越過整個div3載體。當然，它只需要達到number/2。作爲練習留給讀者。

（附加編輯）find3這裏是一個反向迭代器。由於某種原因，似乎是適當的，但我不記得我爲什麼這麼認爲:)如果檢查幷包括number/2，您需要將其更改爲常規轉發迭代器。

#include <iostream> 
#include <vector> 

using namespace std; 

int contains_3 (int value) 
{ 
    while (value && (value % 10) != 3) 
     value /= 10; 
    return value; 
} 

int main (int argc, char **argv) 
{ 
    int number, found_flag, last_div3, adjust, adjust_digit; 
    vector<int> div3; 
    vector<int>::reverse_iterator find3; 
    vector<int>::iterator it; 

    // a little seeding 
    div3.push_back(3); 
    div3.push_back(13); 
    div3.push_back(23); 

    if (argc != 2) 
     return -1; 

    number = atoi (argv[1]); 
    found_flag = 0; 

    // do we need to expand div3? 
    last_div3 = div3.back(); 

    while (last_div3 * 2 < number) 
    { 
    // if this number contains a '3' in any other place than the last, 
    // simply increment it 
     if ((last_div3 % 10) != 9 && contains_3(last_div3/10)) 
     { 
      last_div3++; 
     } else 
     { 
      // no? then simply pick the next multiple of 10 and add 3 
      last_div3 /= 10; 
      last_div3++; 
      last_div3 *= 10; 
      if (!contains_3(last_div3)) 
       last_div3 += 3; 
     } 
    // check if it should be in the list 
     for (it = div3.begin() ; it != div3.end() && (last_div3 % *it); ++it) ; 
     if (it == div3.end()) 
     { 
      div3.push_back(last_div3); 
     } 
    } 

    cout << "list is now: "; 
    for (it = div3.begin() ; it != div3.end(); ++it) 
     cout << ' ' << *it; 
    cout << endl; 

    for (find3 = div3.rbegin(); !found_flag && find3 != div3.rend(); find3++) 
    { 
     if (!(number % *find3)) 
     { 
      cout << "candidate: " << *find3 << ", remaining to sieve: " << number/(*find3) << endl; 

      found_flag++; 
     } 
    } 

    if (!found_flag) 
     cout << "None found" << endl; 

    return 0; 
}