Over a million developers have joined DZone.

Generate Prime Numbers

·
GenPrime(int n) generates all prime numbers smaller or equal to n, storing them in prime[]. NrPrime is the number of prime numbers calculated.

This uses the "Primes Sieve of Eratosthenes".


#include 

int prime[78498]; // 78498 is the number of prime numbers smaller than 1 000 000.
int nrPrime = 0;

void genPrime(int n) {
  char p[1000001];

  memset(p, 1, sizeof(char) * (n + 1));

  p[1] = 0;

  int i = 2;
  for (; i <= n; ++i)
    if (p[i]) {
      prime[nrPrime] = i;
      ++nrPrime;
      int j = i * 2;
      while (j <= n) {
        p[j] = 0;
        j += i;
      }
    }
}
Topics:

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}