Just anoter prime generator

Forum 2005-2010 (read only) General Exhibition
1

The world would probaly be a better plece without it.....

// Prime generator
// Crude and dirty

const unsigned long primeMax = 10000;
unsigned long i, j;
boolean prime;

void setup(){
  Serial.begin(9600);
  Serial.println(2);
  
  for (i = 3; i < primeMax; i=i+2){
    prime = true;
    for (j = 3; j < sqrt(i)+1; j=j+2){
      if (i%j == 0){
        prime = false;
        break;
      }
    } 
    if (prime == true) Serial.println(i);
  }
}

void loop(){}

-Fletcher

Update - code performance:
primeMax set to 30000

Normal code: 29.1 sec
sqrt(i)+1 outside loop: 27.7 sec
sqrt(i)+1 and change to unsigned int: 22.7 sec

2

How was the performance?

3

You would do better if you calculated sqrt(i)+1 prior to executing the inner loop. That way you don't calculate this on every loop of j.

A bigger boost in speed is realized by changing the variables i & j
to unsigned int's, instead of being unsigned longs.

4

Update in post 1.

-Fletcher

5

Change the bit rate from 9600 to 115200. :slight_smile:

6

Current code:

const unsigned int primeMax = 30000;
unsigned int i, j, jMax;
boolean prime;

void setup(){
  Serial.begin(115200);
  Serial.println(2);
  
  for (i = 3; i < primeMax; i=i+2){
    prime = true;
    jMax = sqrt(i)+1;
    for (j = 3; j < jMax; j=j+2){
      if (i%j == 0){
        prime = false;
        break;
      }
    }
    if (prime == true) Serial.println(i);
  }
Serial.println();  
Serial.println(millis());
}


void loop(){};

Serial changed to 115200: 6.78 sec ..... much faster
and with unsigned long: 13.2 sec

7

Serial changed to 115200: 6.78 sec ..... much faster

That was the main thing I learned when I wrote my first prime number generator; that actually outputting the numbers was very expensive compared to computing them. (for a six-digit prime number, you're looking at a couple thousand instructions to test its primeness, max. But each digit output to my terminal was probably a similar number of instructions within the system call, plus context switches between operating system and user process (this was on a mainframe), plus actually dealing with a relatively complex IO device, plus, plus...

8

Last mod -- removed call to sqrt() and replaced it with code to keep track
of when 'i' got to or passed a new square (1,4,9,16,25, etc). If this
happens I bump the Jmax and bumped to the next square. Easy to do
when you know how to figure what the next square is. Got my time down
to 5913-mSec.

Need to replace the (i%j == 0) to get any more speed.

It's been fun!

9

forgive the simple question.....
but why?
I may be missing the obvious...what is the purpose? Thank you.

10

Simple answer, Byron.... why not? :smiley:
Just a little friendly competition at optimizing code for speed
and learning new techniques.

@Fletch' -- Here's my latest code:

// Prime generator
// Crude and dirty

const unsigned int primeMax = 30000;
unsigned int i, j;
unsigned int Jmax, next_sq;
//unsigned long start;
boolean prime;


void setup()
{
  Serial.begin(115200);
  Serial.println(2);
  next_sq = 4;
  Jmax = 2;
  for (i=3; i < primeMax; i+=2){
//    sqrrt = isqrt(i)+1;
    if (i >= next_sq) {
        next_sq += 2*Jmax + 1;
        Jmax++;
    }

    prime = true;

    for (j = 3; j < Jmax; j+=2){
      if (i%j == 0){
        prime = false;
        break;
      }
    }
    if (prime == true)
      Serial.println(i);
  }

  Serial.print(millis());
  Serial.println("-mSec");
}

void loop()
{
}
11

aha. that's well enough. competition :slight_smile:

12

Almost like the superPI program to do benchmarks on the computer. :wink: how long do you think it might take an arduino to calculate one million digits of pi? ;D

13

Hi

The original code took around 40 min to 1/2 million.

Humm, since Rusty is improving with some slick square optimizing I better look into this again :o

Memory is rather limitet but it should be possible to store the first 500 primes (as unsigned integer ~ 1 kb ) in a list and divide a prime candidate with the list before change to sieveing.

I need more sparetime....

-Fletcher