The other, faster program (which i changed a little to add a timer):
Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <iostream>
using namespace std;
typedef unsigned long long bignum;
struct primerec
{
bignum bn;
struct primerec * next;
};
void printPrime(bignum bn)
{
static char buf[1000];
sprintf(buf, "%ull", bn);
buf[strlen(buf) - 2] = '\0';
printf("%s\n", buf);
}
void freeList(struct primerec *head)
{
struct primerec *thisPrime = head;
while(1)
{
struct primerec *nextPrime = thisPrime->next;
free(thisPrime);
if(nextPrime == NULL)
break;
else
thisPrime = nextPrime;
}
}
void findPrimes(bignum topCandidate)
{
struct primerec *firstPrime = (primerec*) malloc(sizeof(struct primerec));
assert(firstPrime != NULL);
struct primerec *latestPrime = firstPrime;
firstPrime->bn = 2;
firstPrime->next=NULL;
bignum candidate = 2;
while(candidate <= topCandidate)
{
struct primerec *thisPrime = firstPrime;
int prime = 1;
while(thisPrime->bn * thisPrime->bn <= candidate)
{
if(candidate % thisPrime->bn == 0)
{
prime = 0;
break;
}
thisPrime = thisPrime->next;
}
if(prime)
{
printPrime(candidate);
latestPrime->next = (primerec*) malloc(sizeof(struct primerec));
assert(latestPrime->next != NULL);
latestPrime = latestPrime->next;
latestPrime->bn = candidate;
latestPrime->next = NULL;
}
candidate++;
}
freeList(firstPrime);
}
int main(int argc, char *argv[])
{
time_t start,end;
time (&start);
bignum topCandidate = 1000;
if(argc > 1)
topCandidate = atoll(argv[1]);
findPrimes(topCandidate);
time (&end);
double dif = difftime (end,start);
cout << dif << endl;
return 0;
}