gistfile1.c

#include<math.h>
#include<stdio.h>
#include<stdlib.h>

int prime_bound(int n)
{
	return n / log(n) + (n / log(n) / log(n));
}

int powmod(int b, int e, int m)
{
    int accum;
    for (accum=1; e > 0; e>>=1)
    {
        if (e & 1) accum = accum * b % m;
        b = (b * b) % m;
    }
    return accum;
}

int ds[] = {2, 7, 61, 0};

int is_prime(int n)
{
	int m = n - 1;
	int s;
	int i, j;
	for (s=0;m % 2 == 0;s++) m >> 1;
	for (i=2;ds[i];i++)
	{
		if (powmod(ds[i], m, n) != 1)
		{
			for (j=0;j<s;j++)
			{
				if (powmod(ds[i], m * (1 << j), n) == n - 1)
				{
					return 1;
				}
			}
		}
	}
	return 0;
}

void show_prime(int bound)
{
	int primes[257] = {};
	int i, n;
	if (primes == 0) return;
	primes[0] = 2;
	printf("%d\n", primes[0]);
	for (n=3; n <= bound; n+=2)
	{
		for (i=1; primes[i]; i++)
		{
			if (n % primes[i] == 0) break;
		}
		if (primes[i] == 0)
		{
			if (i < 256)
			{
				primes[i] = n;
				printf("%d\n", n);
			}
			else if (is_prime(n)){
				printf("%d\n", n);
			}
		}
	}
}

int main()
{
	show_prime(2147483647);
}