Prime Number Generator

This is an Arduino version of the Sieve of Eratosthenes. A reasonably fast prime number generator.

What can you do with prime numbers? It's hard to say outside of cryptography, but maybe try replacing some of those random calls with prime numbers and see if you like your sketch better.

In general people seem to find pink noise (numbers that are somewhat correlated), more aesthetic than white noise (perfectly random numbers). The odds are that the same thing will be true for prime numbers, which are after all are perfectly correlated, just in a way that no one seems to be able to predict.


/*
 * PrimeSieve
 * Paul Badger 2009
 * Generates prime numbers less than 63,001 as shown
 * To extend just add more primes to prime table (and choose a larger data type)
 * The program will generate primes up to the square of the last prime table entry
 */

// just add more primes to the prime table for larger search
// byte data type to save memory - use a larger datatype with prime table entries above 255 :)
byte primes[]={ 
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
    102, 107, 109, 113, 127, 131,  137 , 139, 149, 151, 157, 163, 167, 173,  179, 181, 191, 193, 197, 
    199, 211, 223, 227, 229, 233, 239, 241, 251 };

// if you change the datatype of primes array to int, change next line to 
// "const int TopPrimeIndex = (sizeof(primes)/2) - 1;"

const unsigned int TopPrimeIndex = sizeof(primes) - 1;      
const unsigned long TopPrimeSquared = (long)primes[TopPrimeIndex] * (long)primes[TopPrimeIndex];
int primeFlag;


void setup()                   
{
    Serial.begin(9600);

    Serial.print("Number of primes in prime table = ");
    Serial.println(TopPrimeIndex);
    Serial.println();
    Serial.print("Last prime in table =  ");
    Serial.println((unsigned int)primes[TopPrimeIndex]);
    Serial.println();

    Serial.print("Calculating primes through ");
    Serial.println(TopPrimeSquared);
    Serial.println();


}
void loop()                     // run over and over again
{
    for (long x = 1; x < TopPrimeSquared; x+=2){  // skips even numbers, including 2, which is prime, but it makes algorithm tad faster

            for (long j=0; j < TopPrimeIndex; j++){
            primeFlag = true;

            if (x == primes[j]) break;

            if (x % primes[j] == 0){     // if the test number modolo (next number from prime table) == 0 
                primeFlag = false;       //  then test number is not prime, bailout and check the next number
                break;
            }
        }
        if (primeFlag == true){           // found a prime - print it
            Serial.println(x);
       }
    }
}

Share