Article 122 - Efficient Prime Number Generator

In a previous article, a generic prime number generator was given. In this article, a more efficient algorithm is given.

The reader is encouraged to review the generic prime number generator in Article 111 - Prime Number Generator.

In the basis of prime numbers, the root form of divisors are always prime numbers themselves. The reader can verify a few numbers to test this idea.

Why does this matter?

If a number has a particular divisor, then the divisor is either a prime number or a composite number. Recall a composite number is not a prime number, it has divisors other than 1 and itself.

And if the divisor in question is not a prime number, then it can be further divided recursively into a prime number.

It follows that if none of the prime numbers less than the current number in question is not a divisor, then the current number is a prime number.

An efficient prime number generator.

Node * efficientPrimeNumberGenerator(){
    unsigned int number;
    unsigned int divisor;
    Node * primeNumberList = 0;
    Node * nodePointer;
    int passed;

    for( number = 3; number > 2; number += 2 ){
        passed = 1;

        for( nodePointer = primeNumberList; nodePointer; 
            nodePointer = nodePointer->next ){
            if( number % nodePointer->content == 0 ){
                passed = 0;
                break;
            }
        }

        if( passed ){
            nodePointer = newNode( number );

            if( !nodePointer ){
                return primeNumberList;
            }

            addNode( &primeNumberList, nodePointer );
        }
    }

    return primeNumberList;
}

Comments (0)

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.