building prime table

prime.cpp

/*
 * building isprime table and prime_seq table
 * build 10^6 isprime + prime_seq table cost  <0.1 sec
 * seq_top means the total numer in prime_seq ( 1~10^6 : 78498 prime )
 * isprime: false false true true false TRUE ...
 *            0     1    2    3     4    5
 * prime_seq: 2 3 5 7 11 13 ...
 *
 * example:
 * 1. check if 234567 is a prime => Yes
 * 2. print the first 15 primes
 */
#include <cstdio>
#include <algorithm>

#define TAB_SIZ 1000000
#define SEQ_SIZ 78498	/* check seq_top if TAB_SIZ change */

using namespace std;

int seq_top;
bool isprime[TAB_SIZ];
int prime_seq[SEQ_SIZ];

void set_prime_table()
{
	int num, mul;
	seq_top = 0;
	fill(isprime, isprime+TAB_SIZ, true);
	isprime[0] = false, isprime[1] = false;
	for(num=2;num<TAB_SIZ;num++){
		if(isprime[num] == true){	/* num is a prime */
			prime_seq[seq_top++] = num;
			/* mark all mutiple of num as false */
			for(mul = num<<1; mul<TAB_SIZ ; mul+=num)
				isprime[mul] = false;
		}
	}
}

int main()
{
	set_prime_table();

	/* isprime table */
	const int val = 23567;
	printf("check if %d is prime:\n", val);
	if(isprime[val] == true)
		printf("%d is a prime.\n", val);
	else /* if isprime[val] == false */
		printf("%d is not a prime.\n", val);
	putchar('\n');

	/* prime_seq table */
	int i;
	const int n = 15;
	printf("first %d prime:\n", n);
	for(i=0;i<n;i++){
		if(i)	putchar(' ');
		printf("%d", prime_seq[i]);
	}
	putchar('\n');

	return 0;
}