CODEWITHSUNDEEP
c
Stackbeans
Stackbeans

Reputation: 279

Calculating primes using wiki algorithm

I have just started using C and I am currently working on calculating primes using the wikipedia algorithm here:

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.

When I try implementing what I think turns out like the code above, I get what I believe is an 'infinite loop', where might I have gone wrong?

#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]);
        }


    }
    }

Upvotes: 0

Views: 112

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58241

There's many errors in your code including an empty array, use of pow (which is a floating-point function) and numerous logic errors that deviate from the wikipedia example code.

Here's a corrected, working version that follows the logic of the wikipedia version, with a loop afterwards to print out all the primes less than 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");
}

(Note that a small deviation from the wikipedia algorithm is that this prints primes less than n rather than primes less than or equal to n).

Upvotes: 1

Related Questions