时间戳

首页 > 解决方案 > 使用 wiki 算法计算素数

c - 使用 wiki 算法计算素数

问题描述

我刚刚开始使用 C，我目前正在使用维基百科算法计算素数：

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                A[j] := false

    return all i such that A[i] is true.

当我尝试实现我认为像上面的代码一样的东西时，我得到了我认为是“无限循环”的东西，我可能哪里出错了？

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

int main(void) {
//create empty array to store values
    int isPrime[] = {};
//set a large number
    int n = 1000;
//create for loop
    for(int i = 2; i < n; i++){
///create another for loop taking the exponents
        for(int j = i; j < pow(i, 2); j++){
//if i is equal to j is true then return those values true
        if(isPrime[i] == isPrime[j]){
            printf("%d", isPrime[i]);
        }


    }
    }

标签： c

解决方案

您的代码中有许多错误，包括空数组、使用pow（这是一个浮点函数）以及许多偏离维基百科示例代码的逻辑错误。

这是一个更正的工作版本，它遵循维基百科版本的逻辑，之后有一个循环打印出所有小于 的素数n：

#include <stdio.h>

int main(void) {
  int n = 1000;
  int isPrime[n];
  for (int i = 0; i < n; i++) {
    isPrime[i] = 1;
  }
  for (int i = 2; i * i < n; i++) {
    if (isPrime[i]) {
      for (int j = i * i; j < n; j += i) {
        isPrime[j] = 0;
      }
    }
  }
  for (int i = 2; i < n; i++) {
    if (isPrime[i]) {
      printf("%d ", i);
    }
  }
  printf("\n");
}

（请注意，与维基百科算法的一个小偏差是它打印的素数小于n而不是小于或等于的素数n）。

推荐阅读