找到k個素數的個數;

給定範圍a至b和編號k，找到a至b [包括兩者]之間的所有k-prime數字。 k-prime的定義：如果一個數字具有k個不同的素數因子，那麼它就是一個k-素數。找到k個素數的個數;

即a=4,b=10k=2答案是2。由於6的主要因素是[2,3]，10的主要因素是[2,5]。

現在，這裏是我的嘗試

#include<stdio.h> 
#include<stdlib.h> 
int main(){ 
    int numOfInp; 
    scanf("%d",&numOfInp); 
    int a,b,k; 
    scanf("%d %d %d",&a,&b,&k); 
    int *arr; 
    arr = (int*)calloc(b+1,sizeof(int)); 

    int i=2,j=2,count=0; 
    //Count is the count of distic k prim factors for a particular number 
    while(i<=b){ 
     if(arr[i]==0){ 
      for(j=i;j<=b;j=j+i){ 
       arr[j]++; 
      } 
     } 
     if(i>=a && arr[i]==k) 
      count++; 
     i++; 
    } 
    printf("%d\n",count); 
    free(arr); 

    return 0; 
}

這個問題是從Codechef

這就是我所做的考慮，我把大小B的數組，並從2日開始的每個號碼，我做了以下。

2查看arr[2]是否爲0，然後arr[2]++,arr[4]++,arr[6]++ ....等。

3查看arr[2]是否爲0，然後arr[3]++,arr[6]++,arr[9]++ ....等。

由於arr[4]不爲零，請將其保留。

最後，值arr[i]會給我答案，即arr[2]是1，因此2是1素數，arr[6]是2，因此6是2素數。

問題：

什麼是這個代碼的複雜性，並能在它爲O（n）做什麼？
我在這裏使用動態編程嗎？

來源

2013-07-17 Kraken

這看起來像一個家庭作業問題。你知道如何計算複雜性嗎？ – levengli

@levengli不，它不是作業，我想複雜度會是n/2 + n/3 + n/4 + n/5 ...等等。 – Kraken

@Kraken循環內有一個循環，內部循環的變量取決於外部循環。「O（n^2）」複雜性的標誌。此外，您的縮進可能會更好，但很難閱讀代碼。 –

您正在使用的算法被稱爲Sieve of Eratosthenes。這是一個衆所周知的尋找素數的算法。現在回答你的問題：

1A）什麼是這個代碼

的代碼的複雜性是O(n log(log n))的複雜性。

對於和輸入a和b您的代碼的複雜性是O(b log log b)。運行時間是由於您首先標記了b/2編號，然後b/3，然後b/5等等。所以你的運行時間是b * (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... + 1/prime_closest_to_b)。我們在那裏有一個prime harmonic series，其漸進式增長爲ln(ln(b+1))（請參閱here）。

漸近上限是：

O(b * (1/2 + 1/3 + 1/5 + 1/7 +..)) = O(b) * O(log(log(b+1))) = O(b*log(log(b))

1B）能將它O(n)

要做這是棘手。我想說的是，對於所有實際用途，O(n log log n)算法將會和任何O(n)算法一樣好，因爲log(log(n))增長真的非常慢。

現在，如果我的生命依賴於它，我會嘗試查看是否可以找到一種方法來生成所有數字，其中每個操作都會生成一個唯一的數字，並告訴我它有多少個獨特的素數因子。

2）我在這裏使用動態編程嗎？從維基百科動態規劃的

定義說：

動態編程是通過將它們分解成更簡單的子問題
解決複雜問題的方法

的定義很寬泛，所以這是很遺憾開放解釋。我會說這不是動態編程，因爲你不會將你的問題分解成更小的更小的子問題，並使用這些子問題的結果來找到最終答案。

來源

2013-07-17 17:06:35 cyon

找到k個素數的個數;

回答

相關問題