Using Only Primes As Divisors in C


#include
#include
#include
#include

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 = 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 = 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[])
{
bignum topCandidate = 1000;
if(argc > 1)
topCandidate = atoll(argv[1]);
findPrimes(topCandidate);
return 0;
}

No comments:

Post a Comment