2016-02-21 42 views
0

我已經開始練習我朋友的學校任務,但我一度陷入困境。我認爲我的代碼是正確的,但是如果我看到結果,絕對不會。 我的問題是以下。該程序必須從1到一個自然數,並找到具有該除數的最少數作爲當前數。 例如:[1; 1],[2; 2],[3; 4],[4; 6],[5; 16],[6; 12] ,因爲12是具有6除數。 額外的要求是找到所有的約100約數約。一個標準5分鐘,不是太快,不太慢的PC。 但是,如果我運行的代碼,它堅持在第23號,並無法走得更遠。 我試圖用條件縮短操作數(如果當前的數字比當前需要的更多的除數,它打破了循環),但它沒有任何區別,我不知道爲什麼不能這樣做,找到正確的號碼並繼續。 如果有人能幫助我,我將不勝感激。 在此先感謝!java除數查找需要無限時間

public static String message (int numb){ 
    String[] messages = new String[4]; 
    messages[0] = "Working..."; 
    messages[1] = "Done!"; 
    messages[2] = "Please give the interval! [1-100]"; 
    return messages[numb]; 
} 
public static int intervIn(){ 
    Scanner sc = new Scanner(System.in); 
    int inter = sc.nextInt(); 
    sc.close(); 
    return inter; 
} 
public static int finding (int need){ 
    int divisor = 1; 
    int out=1; 
    if (need!=1){ 
     for (;out<2147483647;){ 
      for (int i = 2;i<=out/2;i++){ 
       if (out%i!=0){ 
        } 
       else { 
        divisor++; 
        if (divisor>=need){ 
         break; 
        } 
       } 
      } 
      divisor++; 
      if (divisor==need){ 
       break; 
      } 
      else { 
       divisor=1; 
       out++; 
      } 
     } 
    } 
    return out; 
} 
public static int[][] doit (int row, int column){ 
    int[][] arrayN = new int[row][column]; 
    int divisorNeed = 1; 
    for (int k = 0;k<row;k++){ 
     arrayN[k][0]=divisorNeed; 
     arrayN[k][1]=finding(divisorNeed); 
     divisorNeed++; 
    } 
    return arrayN; 
} 

public static void main(String[] args) { 
    System.out.println(message(2)); 
    int intervIn = intervIn(); 
    System.out.println(message(0)+'\n'); 
    int[][] arrayNRevis = doit(intervIn,2); 
    System.out.println(message(1)); 
    for (int i=0;i<intervIn;i++){ 
     System.out.print("["); 
     for (int j=0;j<2;j++){ 
      System.out.print(arrayNRevis[i][j]+" "); 
     } 
     System.out.println("\b]"); 
    } 
} 

現在輸出(經過近8小時..):

請給時間間隔! [1-100] 100 Working ...

[1; 1] [2; 2] [3; 4] [4; 6] [5; 16] [6; 12] [7; 64] [ 8; 24] [9; 36] [10; 48] [11; 1024] [12; 60] [13; 4096] [14; 192] [15; 144] [16; 120] [17; 65536] [18; 180] [19; 262144] [20; 240] [21; 576] [22; 3072]

回答

0

每個自然數N可以表示爲升高到某些權力k_i素數p_i的乘法其中k_i >= 0。因此,讓我們說你有個數n等於:

N = P_1^* K_1 P_2^K_2 * ... *^p_z k_z

這一數字將有(k_1+1)*(k_2+1)*...*(k_z+1)分隔,例如

18 = 2^1 * 3^2

和具有(1 + 1)*(2 + 1)分隔器或分隔器6:1,2,3,6,9,18,

素數可使用篩算法(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

然後你可以使用動態編程來計算給定數量n的分頻器的數量預計算。如果n = n_1 * p_i^k_i(n可以除以p_i^k_i),則n的分隔符的數量是n_1 *(k_i + 1)的分隔符的數量。

這應該加快分頻計數的計算。

0

很明顯,你沒有卡在第23號,但它將需要大約120小時來評估它。請參閱http://oeis.org/A005179

這是一個APL NARS2000工作區,可以加快速度。 第一個100只需要1/10秒。

 )WSID 
C:\Users\Ab\AppData\Roaming\NARS2000\workspaces\combfactor 

    )FNS 
combfactor factors listws  save                        

    )VARS 
COMBFACTOR DESCRIBE  DIV   RESULTSfor100                  

    ∇ z ← combfactor n;f;p 
[1] f ← (⊂,n),factors n  ⋄ ⍝ find all factors combinations of n 
[2] p ← ⍸0π⍳¯2π32   ⋄ ⍝ The first 32 primes numbers 
[3] z ← ((⍴¨f)↑¨⊂⍟p)+.רf-1 ⋄ ⍝ give ratios of all combinations 
[4] z ← ∊¯1+((⌊/z)=z)/f  ⋄ ⍝ get the combination with minimum ratio 
[5] z ← (0x+(⍴z)↑p)×.*z  ⋄ ⍝ evaluate p_1^(f_1-1) * p_2^(f_2-1) * ... * p_n^(f_n-1) 
    ∇ 

    ∇ z ← {fmax} factors n;f;d 
[1] :if 0 = ⎕NC 'fmax' ⋄ fmax ← 2*63 ⋄ :endif 
[2] z ← ⍬ ⋄ f ← ⌊fmax⌊n÷2 
[3] :while f ≥ 2 
[4]  :if 0 = f∣n 
[5]  d ← n÷f ⋄ :if d ∧.≤ f,fmax ⋄ z ,← ⊂f,d ⋄ :endif 
[6]  z ,← f,¨f factors d 
[7]  :endif ⋄ f -← 1 
[8] :endwhile 
    ∇ 

     COMBFACTOR 
RESULTSfor100 ← ⍪(,¨⍳100),¨combfactor¨,¨⍳100 ⋄ ⍝ 0.1 second 

     DESCRIBE  
DESCRIBE                    
⍝ def factors(number, max_factor=sys.maxint):           
⍝  result = []                  
⍝                      
⍝  factor = min(number/2, max_factor)            
⍝  while factor >= 2:                
⍝   if number % factor == 0:              
⍝    divisor = number/factor            
⍝                      
⍝    if divisor <= factor and divisor <= max_factor:       
⍝     result.append([factor, divisor])          
⍝                      
⍝    result.extend([factor] + item for item in factors(divisor, factor))  
⍝                      
⍝   factor -= 1                 
⍝                      
⍝  return result                 
⍝                      
⍝ print factors(12) # -> [[6, 2], [4, 3], [3, 2, 2]]         
⍝ print factors(24) # -> [[12, 2], [8, 3], [6, 4], [6, 2, 2], [4, 3, 2], [3, 2, 2, 2]] 
⍝ print factors(157) # -> []               

     DIV   
divisors←{z[⍋z←∊∘.×/1,¨(∪π⍵)*¨⍳¨∪⍦π⍵]} 

     RESULTSfor100 
    1 1        
    2 2        
    3 4        
    4 6        
    5 16        
    6 12        
    7 64        
    8 24        
    9 36        
    10 48        
    11 1024       
    12 60        
    13 4096       
    14 192       
    15 144       
    16 120       
    17 65536       
    18 180       
    19 262144       
    20 240       
    21 576       
    22 3072       
    23 4194304      
    24 360       
    25 1296       
    26 12288       
    27 900       
    28 960       
    29 268435456      
    30 720       
    31 1073741824      
    32 840       
    33 9216       
    34 196608       
    35 5184       
    36 1260       
    37 68719476736     
    38 786432       
    39 36864       
    40 1680       
    41 1099511627776     
    42 2880       
    43 4398046511104     
    44 15360       
    45 3600       
    46 12582912      
    47 70368744177664     
    48 2520       
    49 46656       
    50 6480       
    51 589824       
    52 61440       
    53 4503599627370496    
    54 6300       
    55 82944       
    56 6720       
    57 2359296      
    58 805306368      
    59 288230376151711744    
    60 5040       
    61 1152921504606846976   
    62 3221225472      
    63 14400       
    64 7560       
    65 331776       
    66 46080       
    67 73786976294838206464   
    68 983040       
    69 37748736      
    70 25920       
    71 1180591620717411303424   
    72 10080       
    73 4722366482869645213696   
    74 206158430208     
    75 32400       
    76 3932160      
    77 746496       
    78 184320       
    79 302231454903657293676544  
    80 15120       
    81 44100       
    82 3298534883328     
    83 4835703278458516698824704  
    84 20160       
    85 5308416      
    86 13194139533312     
    87 2415919104      
    88 107520       
    89 309485009821345068724781056 
    90 25200       
    91 2985984      
    92 62914560      
    93 9663676416      
    94 211106232532992    
    95 21233664      
    96 27720       
    97 79228162514264337593543950336 
    98 233280       
    99 230400       
    100 45360 

這裏是採取62微秒 C程序!

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define min(a,b) (((a) < (b)) ? (a) : (b)) 
#define MaxInt 0x7fffffffffffffff 
#define ll long long 

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 
       67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131}; 

ll minimums[16]; // contains minimum for each level 

ll ipow(ll base, int exp) { 
    ll result = 1; 
    while (exp) { 
     if (exp & 1) result *= base; 
     exp >>= 1; base *= base; 
    } return result; 
} 

ll factors(ll number, ll max_factor, int level) { 
    ll result = MaxInt; 
    ll factor = min(number/2, max_factor); 
    while (factor >= 2) { 
     if (number % factor == 0) { 
      ll divisor = number/factor; 
      ll tempf = ipow(primes[level], factor-1); 

      if (divisor <= factor && divisor <= max_factor) { 
       ll tempd = ipow(primes[level+1], divisor-1); 
       minimums[level] = min(minimums[level], tempf * tempd); 
      } 
      ll fct = factors(divisor, factor, level+1); 
      if (fct < MaxInt) 
       minimums[level] = min(minimums[level], tempf * fct); 

      result = minimums[level]; 
      minimums[level+1] = MaxInt; 
     } 
     factor -= 1; 
    } 
    return result; 
} 

ll fact(int number) { 
    for (int level = 0; level < 16; level++) minimums[level] = MaxInt; 

    ll res = factors(number, MaxInt, 0); 
    if (res < MaxInt) return res; 
    else    return 0; 
} 

int main(int argc, char *argv[]) { 
    int N = 100; 
    if (argc > 1) N = atoi(argv[1]); 

    ll res[N]; 
    clock_t Start = clock(); 
    for(int n = 1; n <= 10000; n++) 
     for (int i = 1; i <= N; i++) res[i] = fact(i); 
    printf("\n%0.6f second(s)\n", (clock() - Start)/1000.0/10000.0); 

    for (int i = 1; i <= N; i++) 
     if (res[i] > 0) printf("%d %lld\n", i, res[i]); 
     else if (i > 64) printf("%d 2 power %d\n", i, i-1); 
      else   printf("%d %lld\n", i, ipow(2, i-1)); 
    return 0; 
}