2016-02-21 43 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; 
}