Go Down

### Topic: Simple prime number printer (Read 3954 times)previous topic - next topic

#### Chicken325

##### Jun 04, 2011, 06:16 pm
Since I don't have any hardware yet, I decided to do programming instead.  I created a simple program that echoes a prime number every second, unless it took longer than a second to calculate it. (It would take an EXTREMELY long time to get that far.)  The delay is editable.  The program is 2548 bytes when compiled. It uses what is probably a well known algorithm to find prime numbers. (I just made it up, I'm sure this method already exists)  I know it's not much, but it's the first thing I've ever done on an Arduino besides making a light blink, so I'm happy with it!
Code: [Select]
`int count = 2; //Start at 2- 1 doesn't countint printDelay = 1000; //Minimum prime number delayvoid setup() {  Serial.begin(9600);  Serial.println("Starting...");}void loop() {  unsigned long start = millis();  if(isPrime(count)) {    Serial.println(count);        if(millis() - start < printDelay) {      delay(abs(printDelay - (millis() - start)));    }  }  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;}`

This program could be edited to be a benchmark-type program for Arduinos.

#### carl47

#1
##### Jun 06, 2011, 07:27 am
Neat little program.

You are on your way to much fun with arduino.

Prime numbers are great check out:

#### Oracle

#2
##### Aug 14, 2011, 05:53 pm
Cute little project.  Primes are a lot of fun to play with.

When you count through your for loop, you don't need to compare any even numbers (after 2), so you can increment by 2 which should double your program's speed.

If a number is not prime, it will have factors that are prime, so if you want to get a lot more advanced and a lot faster, you can keep a table of all the primes you've already computed and iterate through those instead of testing every odd number every time.  That gets into a programming technique called "dynamic programming".

#### robtillaart

#3
##### Aug 14, 2011, 07:35 pm

Another optimization you only have to test until sqrt(x) +1,

number bigger than sqrt(x) can't be a divider of x unless there is a number smaller than sqrt(x) that is a divider. // the +1 is to handle rounding errors

if (count % 2 ==0) return false;
for(int i = 3; i <= sqrt(x)+1; i+=2)

More prime optimizations see my remarks - http://arduino.cc/forum/index.php/topic,63071 -
Rob Tillaart

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

#### Udo Klein

#4
##### Aug 14, 2011, 08:46 pm
I would not computer sqrt at all. Instead I would only check till i*i > x. This can be computed without any multiplications because:

(n+1)*(n+1) = n*n+2*n+1, thus

n_0 := 0,
n_(i+1) := n_i+2*i+1 = n+i+i+1

Hence successive square numbers can be computed by addition.

#### robtillaart

#5
##### Aug 15, 2011, 11:29 am
good point Udo!
Rob Tillaart

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

#### Udo Klein

#6
##### Aug 15, 2011, 05:25 pm
This is an "old school" assembler code trick

#### Udo Klein

#7
##### Aug 15, 2011, 05:28 pm
Oops forgot to mention: the recursion is an inhomogenous recurrence equation. Thus the mathmaticians knew this way before this newfangled computer stuff was invented

#### robtillaart

#8
##### Aug 15, 2011, 07:08 pm
Many math that is invented/discovered has no direct purpose, and someday someone find a use for it. Sometimes that takes decades.

In the Scientific American August 2011 p60++ an interesting article about "Why Math Works", subtitle "is math invented or discovered?" discusses some nice cases.

Rob Tillaart

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

#### Udo Klein

#9
##### Aug 15, 2011, 07:41 pmLast Edit: Aug 15, 2011, 07:45 pm by Udo Klein Reason: 1
Decades??? Pfft. Think about number theory --> centuries to applications. Millenia to resolution (e.g. transcendence of pi). Others still open probably for a long time to come (Riemann's hypothesis).
Still a lot of stuff to discover or to invent.

I think at the cutting edge it is invention. Once a theory gets hardened discovery follows. What was the point of the article?

#### robtillaart

#10
##### Aug 15, 2011, 08:08 pm

It is a mixture of invention and discovery. Concepts are invented, and then the underlying relations are discovered. They follow from the concept. (e.g. complex number theory, the concept is sqrt(-1) == i  and we display it in a plane iso line .

Another question the author asks is what gives mathematics its explanatory and predictive powers? But there is no definitive answer to that one.

Start of the article - http://www.scientificamerican.com/article.cfm?id=why-math-works -
Rob Tillaart

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

#### bilbo

#11
##### Aug 16, 2011, 09:53 pm
I read that article too -- and thought of it in this thread. A great article that really makes you think.

Basically, it said that the ability of math to predict and explain things (that sometimes havent even been discovered yet) means that it must be natural. What we create is the language used to express it, but not its fundamental concepts.
Alice asked the Chesire Cat, who was sitting in a tree, "What road do I take?"
The cat asked, "Where do you want to go?"
"I don't know," Ali

#### Udo Klein

#12
##### Aug 17, 2011, 09:31 pm
Interestingly the article cites Einstein but does mention that he also pondered:

Quote
Insofern sich die Sätze der Mathematik auf die Wirklichkeit beziehen, sind sie nicht sicher, und insofern sie sicher sind, beziehen sie sich nicht auf die Wirklichkeit.

Which is usually translated as

Quote
"As far as the laws of mathematics refer to reality, they are not certain, as far as they are certain, they do not refer to reality."

The power of mathmatics is indeed enormous. However if it fails this is usually not attributed to mathmatics but to model flaws. Thus the predictive power is somehow tautological.

Go Up

Please enter a valid email to subscribe