/* atk1 h8t2 -- alkulukutesti */

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

#define N 100

/* etsii i:nnen alkuluvun, kun i-1 ensimmäistä alkulukua
on löydetty ja taulukoitu taulukkoon, jonka tämä funktio
saa 1. argumentikseen. 2. argumentti on i */
void find_ith_prime(int*,int);
int isprime(int j,int* primes); /* palauttaa 1 jos 
j on alkuluku. testaa jaollisuuden vain primes-taulukon alkioilla */
void prn(int*); /* tulostaa taulukon sisällön */
void analyze(int*); /* laskee esim. alkulukutiheyden */

main()
{
	/* annetaan muutama ensimmäinen alkuluku taulukolle
	pesämunaksi (tarvitaan väh. yksi) */
	int primes[N+1]={2,3,5};
	int i=0,n;

	/* jos annettiin alkulukutaulukolle alku, niin pannaan
	indeksi i vastaamaan tätä */
	while(primes[i]!=0)
		i++;

	printf("How many primes? (Max. %d. Enter 0 to fill the table) ",N);
	scanf("%d",&n);

	if(n==0)
		while(i<N)
		{
			find_ith_prime(primes,i);
			i++;
		}
	else
		while(i<n)
		{
			find_ith_prime(primes,i);
			i++;
		}

	prn(primes);
	analyze(primes);
}

int isprime(int j,int* primes)
{
	/* alkulukutesti: jos j ei ole jaollinen millään itseään 
	pienemmällä alkuluvulla, niin se on itse alkuluku. käydään
	siis läpi kaikki tähän asti löydetyt alkuluvut */
	int k;
	for(k=0;primes[k]!=0 && primes[k]<=sqrt((double)j);k++)
	{
		/* x on jaollinen y:llä jos x%y==0 (jakojäännös, kun
		x jaetaan y:llä */
		if(j%primes[k] == 0)
		{
			return 0;
		}
	}
	/* jos päästään tänne, niin j ei ole ollut jaollinen millään
	primes-taulukon luvulla => se on alkuluku */
	return 1;
}

void find_ith_prime(int* primes,int i)
{
	int j;

	if(i==0)
		j=2;
	else
	{
		/* aloitetaan uuden alkuluvun etsiminen 
		(edellinen alkuluku + 1) :sta */
		j=primes[i-1]+1;
		while(!isprime(j,primes))
		{
			/* kasvatetaan j:n arvoa, kunnes se todetaan alkuluvuksi */
			j++;
		}
	}

	primes[i]=j;
}

/* tulostaa nollasta poikkeavat alkiot */
void prn(int* primes)
{
	int i=0;

	printf("\n%10s%10s\n","Prime #","Value"); /* otsakkeet */

	for(i=0;primes[i]!=0;i++)
		printf("%10d%10d\n",i+1,primes[i]);
}

void analyze(int* primes)
{
	int i;
	double density;

	/* haetaan taulukon viimeinen nollasta poikkeava alkio */
	for(i=0;primes[i]!=0;i++)
		;

	density = (double)i / (double)primes[i-1];

	printf("\nThe %dth prime was %d, so the prime number\ndensity ",i,primes[i-1]);
	printf("around %d is %.4lf.\n\n",primes[i-1],density);
}