DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Generate Prime Numbers

06.22.2007
| 7082 views |
  • submit to reddit
        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 <string.h>

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;
      }
    }
}