Prime number generator in C

Question

Where can I find a prime number generator in C?

Answer 1

Especially for large primes (to used for encryption, etc), I used: the GNU MP Bignum Library.

EDIT: I assumed to question to be about find a random number generator:

Check the methods for Integer Random Numbers to generate random numbers and Number Theoretic Functions to validate their primes:

mpz_t random_prime(mpz_t max) {
    gmp_randstate_t state;
    mpz_t result;

    gmp_randinit_defult(state);
    mpz_init(result);

    while (mpz_probab_prim_p(result, 4) == 0) {
        mpz_urandomm(result, state, max);
    }

    return result;
}

[Haven't run the code myself]

Answer 2

here is one. http://snippets.dzone.com/posts/show/4247

Answer 3

The most "classic" implementation of a prime number generator is the Sieve of Eratosthenes. There are numerous improvements on this algorithm, but it should give you a good start.

Here's a bit of source code (below) from a public domain implementation. [Original link]:

/* This code is in public domain. Use for whatever purpose at your own risk. */
#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define MAXN  100000000  /* maximum value of N */
#define P1    1562501    /* = ceil(MAXN/64) */
#define P2    50000000   /* = ceil(MAXN/2) */
#define P3    5000       /* = ceil(ceil(sqrt(MAXN))/2) */

uint32_t sieve[P1];

#define GET(b) ((sieve[(b)>>5]>>((b)&31))&1)

void make()
{
    uint32_t i, j, k;
    memset(sieve, 0, sizeof(sieve));
    for (k = 1; k <= P3; k++)
        if (GET(k)==0) for(j=2*k+1,i=2*k*(k+1);i<P2;i+=j) sieve[i>>5]|=1<<(i&31);
}

int isprime(int p) { return p==2 || (p>2 && (p&1)==1 && (GET((p-1)>>1)==0)); }

int main()
{
    int i, n;
    make();
    for (n = 0, i = 0; i <= MAXN; i++)
        if (isprime(i)) n++;
    printf("The number of primes below 10^8 is %d.\n", n);
    return 0;
}

Answer 4

int get_prime(void) {
  return 3; /* Prime for all values of 3, including large ones */
}

Oh, you mean want random primes of an arbitrary size?

Answer 5

Using simple loops with division and checking the remainder with a little multi-threading meant I could find the first 1,000,000 primes in 10 seconds on a Q6600 quad-core 2.4GHz processor.

Answer 6

This is a good one: SIMD-oriented Fast Mersenne Twister (SFMT). But overall it depends what you're looking for, as somebody else pointed out. Is it for a homework assignment? Hiding pr0n from your little sister? Looking for the first X-digit prime number in the first million decimal expansion of e for google interviewing..?

Answer 7

void main(void) {

int num,i,len=541;


printf("Prime numbers are: ");
for(num=2;num<=len;num++){
    for(i=2;i<=len;i++){
        if ( num%i == 0){
            if ( num==i )
                printf("%d ",num);
            else             
                break;

        }
    }
}

}