素數編碼

Question

我試圖從在線判斷系統解決一個問題。我有一個可行的解決方案，但效率不夠高。問題是這樣的：

哪一個最少的數字n可以在產品n = a∙b中像k路一樣想象？產品a∙b和b∙a是其中一種方式，其中所有數字都是自然的（1≤k≤50）。

輸入一個數字k。 輸出一個數字n。

我的代碼沒有通過四個測試。這對k = 31,37,47來說太慢了。我一直在考慮這個問題2天，但沒有改進。這是我的代碼，請分享，如果您有任何想法。

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

    int prime[10000]; 
    long x,j,i,flag,k,length,p,checker,count,number; 

    int main() 
    { 

    prime[0]=2; 
    scanf("%ld",&k); 
    //I find prime numbers between 1 and 1000. 1000 can be changed, just for testing 

    for (i=3;i<=1000;i=i+2) 
      { 
      flag=0; 
      for (j=2;j<=sqrt(i);j++) 
        { 
        if(i%j==0) 
          { 
          flag=1; 
          break; 
          } 
        } 
      if(flag==0) 
        { 
        x++; 
        prime[x]=i; 
        } 
      } 

    length=x; 
    //this loop is too big I know, again for testing. I suspect, there must be a way to make some changes to this for loop 

    for (i=1;i<10000000000;i++) 
      { 
      number=i; 
      p=1; 
      for(x=0;x<=length;x++) 
        { 
        if(prime[x]>sqrt(i)) 
        break; 
        count=0; 
        while(number%prime[x]==0) 
          { 
          number=number/prime[x]; 
          count++;  
          } 
        p=p*(count+1); 
//I find prime factors of numbers and their powers, then calculate number of divisors 

        } 
      //printf("%d\n",p); 
      //number of ways is just number of divisors/2 or floor (divisors/2)+1 
      if(p%2==0) 
      checker=p/2; 
      else 
      checker=floor(p/2)+1; 
      if(checker==k) 
        { 
        printf("%ld\n",i); 
        break; 
        } 
      } 

    return 0; 
    } 

Answer 1

如果我理解正確的問題，它問你這是最號n恰好2K除數（我應該考慮1和n？）

事實上，如果一些有除數，然後N/A = b是整數，n = A * b（只計算一次a和b，所以你應該除以二分頻器的數目）

編輯

否則即時間的確費時。所以這是主意。 （a1）* p2 ^（a2）... pn ^（an）（這是數字的素數因式分解）除數的數目是（a1 + a1）* p2 ^（a2）... pn^1）（a2 + 1）...（an + 1）

因此，如果要查找具有k除數k的因數k的數字。然後將最大的因子分配給最小的素數;如果k = 2 * 5 * 7，那麼n應該是2^7 * 3^5 * 5^2

我知道這不是因爲我沒有考慮到（a，b）等於b，A），但它周圍玩一點，它應該工作

例如

取K = 37。然後數量增加一倍 - （考慮對稱性）。你得到了74. 現在，如果你可以想象n = n * 1，那麼你只需要因子74（即2 * 37）; 然後給36到2和1到3，領導n = 2 ^（36）* 3 = 206158430208

如果你不能，那麼你需要添加1到你以前得到的數字（在這種情況下， 74 + 1 = 75 = 25 * 3）;這樣你會得到N = 2^24 * 3^2 = 150994944

如果它沒有上述情況，那麼我可能是錯的...