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)。

我是不是代码写的不好？请告诉我正确的观点...

Answer 1

你的翻译看起来很马虎。

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 开始的数组。

Answer 2

如果你想根据你的需要调整算法，首先逐字实现它总是一个好主意，特别是如果你有足够详细的伪代码允许逐字翻译成 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

和你想要的结果明显不同

C - 使用此算法获取质数

C - getting prime numbers using this algorithm

c

primes