C - 使用此算法获取素数

Question

我正在处理一些简单的问题。 我想质数

我会用这个算法

和...我完成代码编写这样的。

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 ...

Answer 1

如果你想调整一个算法以满足你的需求，首先逐字实现它总是一个好主意，尤其是如果你有足够详细的伪代码来允许这样的逐字转换成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 

这是你想要的结果明显不同。

Answer 2

你的翻译看起来很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的数组。