Hi I've been taking a python course and now that were done the professor wants us to write a program to list all the prime numbers from 2 - 10000. Oh yea and it has to be in C. So I am very stuck and really need help. Heres the assignment:

Write a C program to compute and display all of the prime numbers which are less than 10000 using the technique known as the "Sieve of Eratosthenes". It works as follows:

Start with a list of all candidate numbers up some number N (in this case, integers from 2 to 9999). Set a variable "p" to the first prime number, 2. While p^2 (p squared) is less than N, repeat the following: (1) starting from p^2, calculate all of the multiples of p less than or equal to N and eliminate them from the list; and (2) set p to the next number still on the list. This is the next prime number.

When you are done, the only numbers remaining on the list will be prime.

Heres what I've done so far, Thanks in advanced for the help!

#include <stdio.h>
char numlist[10000];



int main(void){

  int i,p,n;

  for (i=2; i<10000; i++) {
    numlist[i]=1;
  }
  
  p=2;
  n=10000
  
  while (p*p<n) {
  for (p*p<=n; n<10000; p++) {
    numlist[p]=0;
    }
    }

Recommended Answers

All 2 Replies

If you're going to load numlist with the list of primes, the loop

for (i=2; i<10000; i++) {
    numlist[i]=1;
  }

is unnecessary. Also, what values will numlist[0] and numlist[1] contain?


The for statement is wrong for (p*p<=n; n<10000; p++) The first field p*p<=n cannot be a comparison to be useful. And is the comparison field n<10000 a good stopping point?

Now, the question is, how do you tell if a number is prime? That's what goes in the for loop.

#define TRUE 1
// init composite[i] to zero
void FindPrimes(int composite[], int until)
{
 for (int i = 2; i < until; i++)
 {
  // if number i is not composite number or in other words - if it is prime number
  if (!composite[i])
  {
   // find out all multiples of i
   for (int j = i + i; j <= until; j += i)
   {
    composite[j] = TRUE;
   }
  }
 }
}

After this function execution number i will be prime if composite[i]==0 . Optimize this example by your needs (p squared and such).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.