Go Down

Topic: Error in prime printer :( (Read 2170 times) previous topic - next topic

Chicken325

Jun 04, 2011, 05:44 pm Last Edit: Jun 04, 2011, 05:46 pm by Chicken325 Reason: 1
I was making this code to try and print a sequence of primes (Don't tell me whether isPrime() works or not- I want to do that myself without help  :)) however there's this error I can't get rid of.  Do you guys know what's wrong?  Sorry- if it's really obvious, I apologize.  I am experienced in PHP and Java but I'm new to Arduino and electronics in general.

This is the error:
Code: [Select]
prime.cpp: In function 'void loop()':
prime:7: error: 'count' was not declared in this scope
prime:10: error: 'count' was not declared in this scope


And this is the code:
Code: [Select]
void setup() {
 Serial.begin(9600);
 Serial.println("Starting...");
 int count = 2; //Start at 2- 1 doesn't count
}

void loop() {
 if(isPrime(count)) {
   Serial.println(count);
 }
 count++;
}

boolean isPrime(int x) {
 boolean prime = true;
 
 for(int i = 2; i < x/2; i++) { //Loop every number up to half
   if(x % i == 0) { //If it's divisible...
     prime = false; //It isn't prime!
     break;
   }
 }
 
 return prime;
}


Thanks so much!

Chicken325

#1
Jun 04, 2011, 05:53 pm Last Edit: Jun 04, 2011, 06:00 pm by Chicken325 Reason: 1
I found I just had to move count to above setup.  Thanks anyways!  :~

EDIT:  How can I remove this topic? :P

Fletcher_Chr

Hi Chicken325

It's easy for you to improve your prime code.

1) Skip all the even numbers. The number 2 is the only even prime.
2) You can stop at sqr(x). There is no primes between sqr(x) and x/2.

-Fletcher

robtillaart


you might need to add timing info how long it takes to find all the primes. If you have ideas to improve the algorithm you can measure it.

The ideas of Fletcher are good ones. you should try to implement them;


If those work you can make even a faster primefinder.

recall 2x3x5 = 30 
=> if we look at blocks of 30 numbers and filter all multiples of 2,3,and 5 we have this row  [30-60]
31 37 41 43  47 49 53 59  (8 values)

or written otherwise
30 +1 +7 +11 +13 +17 +19 +23 +29

so if you have a loop that makes steps of 30, you only need to check these 8 offsets as the others are divisable by 2,3, or 5. 

checking 8 in 30 = 26.7% of the values, that is almost a factor 2 faster than only checking the odd numbers, which is allready a factor 2 faster than checking all numbers..

The nice part of this trick is that you can encode the set of eight possible primes into one byte. imagine an array in which the arrayindex indicates the numberx30 and every bit indicates one of the eight mentioned offsets. a 1 bit means prime, a 0 bit means no prime. The values 1..60 will give these two bytes:

01111111 11111011  // the first 0 = byte 0 x 30 + offset 1 = 1, the second 0 is byte 1 x 30 + offset 19 = 49

Note the numbers 2,3,5 are not encoded in these bytes.

This way an array of 1000 bytes can hold (encoded) all the primes from 1 - 30.000 !!

Although this trick can be expanded to larger jumps, the number of offsets will increase and the speed improvement is getting less.

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

maniacbug


(Don't tell me whether isPrime() works or not- I want to do that myself without help  :))


Heh, it's too late dude, you let the genie out of the bottle!  ;)

Fletcher_Chr

Hi

Dang Rob, that was advanced optimizing  :smiley-eek:

My advance advice would have been to make a list of known small primes (like all primes from 2-300) and then check a candidate against that list before switching to Eratosthenes sieve.

I once wrote a pyton code that omitted the power hungry modolo operation. You make a list of boolean items in the full range you wanna test and then declare all items "1" (all numbers are primes). Go though the list, if you meet a "1" all multiplication of that number is switched from "1" to "0". After once through the list it will only contain "1" at prime numbers.

As long long as the list chould stay in PC memory without useing swarp files it was super fast.

Oh well, the prime genie is out of the bottle.

-Fletcher

Btw, looks like OP posted the code here:http://arduino.cc/forum/index.php/topic,63073.0.html

Chicken325

Those are some good ideas! I am humbled by your smartitude. (I'm not a math genius) :)

Now that I've got some hardware, I can do more stuff!  I have a screen, buttons, and a joystick.  I'm thinking about making the Ulam spiral and maybe the Game of Life.  I'm interested in those kinds of things.

Go Up