C - 使用此算法獲取素數

我正在處理一些簡單的問題。我想質數C - 使用此算法獲取素數

我會用這個算法
enter image description here

和...我完成代碼編寫這樣的。

int k = 0, x = 1, n, prim, lim = 1; 
int p[100000]; 
int xCount=0, limCount=0, kCount=0; 

p[0] = 2; 
scanf("%d", &n); 

start = clock(); 
do 
{ 
    x += 2; xCount++; 
    if (sqrt(p[lim]) <= x) 
    { 
     lim++; limCount++; 
    } 
    k = 2; prim = true; 
    while (prim && k<lim) 
    { 

     if (x % p[k] == 0) 
      prim = false; 
     k++; kCount++; 
    } 
    if (prim == true) 
    { 
     p[lim] = x; 
     printf("prime number : %d\n", p[lim]); 
    } 
} while (k<n);

欲檢查多少重複這個代碼（X + = 2; LIM ++; k ++;）所以我用XCOUNT，limCount，kCount變量。

當input（n）爲10時，結果爲x：14，lim：9，k：43錯誤的答案。

答案是（14,3,13）。

我寫代碼不好嗎？告訴我正確的點PLZ ...

來源

2017-05-26 COOOPS

最明顯的不同是沒有'for'循環使用'i' –

第一次到達'sqrt（p [lim]）'''p [1]'這是未初始化的。 –

嗯......我想'lim'substitues'我' – COOOPS

如果你想調整一個算法以滿足你的需求，首先逐字實現它總是一個好主意，尤其是如果你有足夠詳細的僞代碼來允許這樣的逐字轉換成C代碼（更是如此按照Fortran但我離題）

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

int main (void){ 
    // type index 1..n 
    int index; 
    // var 
    // x: integer 
    int x; 
    //i, k, lim: integer 
    int i, k, lim; 
    // prim: boolean 
    bool prim; 
    // p: array[index] of integer {p[i] = i'th prime number} 
    /* 
     We cannot do that directly, we need to know the value of "index" first 
    */ 
    int res; 

    res = scanf("%d", &index); 
    if(res != 1 || index < 1){ 
     fprintf(stderr,"Only integral values >= 1, please. Thank you.\n"); 
     return EXIT_FAILURE; 
    } 
    /* 
     The array from the pseudocode is a one-based array, take care 
    */ 
    int p[index + 1]; 
    // initialize the whole array with distinguishable values in case of debugging 
    for(i = 0;i<index;i++){ 
     p[i] = -i; 
    } 
    /* 
     Your variables 
    */ 
    int lim_count = 0, k_count = 0; 

    // begin 
    // p[1] = 2 
    p[1] = 2; 
    // write(2) 
    puts("2"); 
    // x = 1 
    x = 1; 
    // lim = 1 
    lim = 1; 
    // for i:=2 to n do 
    for(i = 2;i < index; i++){ 
     // repeat (until prim) 
     do { 
      // x = x + 2 
      x += 2; 
      // if(sqr(p[lim]) <= x) then 
      if(p[lim] * p[lim] <= x){ 
      // lim = lim +1 
      lim++; 
      lim_count++; 
      } 
      // k = 2 
      k = 2; 
      // prim = true 
      prim = true; 
      // while (prim and (k < lim)) do 
      while (prim && (k < lim)){ 
      // prim = "x is not divisible by p[k]" 
      if((x % p[k]) == 0){ 
       prim = false; 
      } 
      // k = k + 1 
      k++; 
      k_count++; 
      } 
     // (repeat) until prim 
     } while(!prim); 
     // p[i] := x 
     p[i] = x; 
     // write(x) 
     printf("%d\n",x); 
    } 
    // end 

    printf("x = %d, lim_count = %d, k_count = %d \n",x,lim_count,k_count); 

    for(i = 0;i<index;i++){ 
     printf("%d, ",p[i]); 
    } 
    putchar('\n'); 

    return EXIT_SUCCESS; 
}

將打印起始於2

的index - 1數的素數，您可以輕鬆地現在改變 - 例如：只打印素數高達index而不是index - 1素數。

在你的情況下，號碼全部六個素數高達13給出

x = 13, lim_count = 2, k_count = 3

這是你想要的結果明顯不同。

來源

2017-05-26 20:16:50 deamentiaemundi

int * p; p =（int *）malloc（index + 1）;我用這個代碼。然後我輸入11，然後我可以得到（14,3,13）。它是輸入10的答案。但我猜這個代碼是正確的，因爲基於差異1的數組或基於0的數組。非常感謝。 – COOOPS

你的翻譯看起來很sl。。

for i:= 2 to n do begin

必須翻譯成：

for (i=2; i<=n; i++)

repeat 
    .... 
until prim

必須翻譯成：

do { 
    ... 
} while (!prim);

while prim...環路是裏面的環路repeat...until prim。

我把它留給你把它應用到你的代碼，並檢查所有構造已被正確翻譯。這看起來不難做到這一點。

注意：它看起來像算法使用基於1的數組，而C使用基於0的數組。

來源

2017-05-26 16:57:10

我改變了你的代碼。 – COOOPS

但它不符合答案。我想我不能從基於1的數組轉換爲基於0的數組。 – COOOPS

@COOOPS您可以創建一個較大的數組1，並且只是簡單地不使用第一個位置作爲初始階段。基於1和基於0的轉換不是一個簡單的問題，據我所見，在C++和Matlab之間進行轉換... –

C - 使用此算法獲取素數

回答

相關問題