Has anyone made a prime number Generator?

Prime number generators have been around in other programming languages for awhile now, but not very useful for finding prime numbers with more than 7 digits. (Prime95 does that).
Has this ever been done with the arduino? If not then it must be done! The arduino simply must venture everywhere! It already went into space! Why not prime numbers?

Who knows the code might be useful for.....okay i give up. But this is bar sport so..

Hypothetical code:

1.Have a Prime number bank to store all prime numbers generated
2.Put numbers 1 and 2 into the bank
3.make an int = 3
Have code start at 3 but skip all even numbers
4.Analyze Number, if divisible by any number in the bank then move onto next loop, if all come out as floating point then store number into bank and serial print it.
5. Increment the int
6. Loop

:smiley: ;D :-?

Has this ever been done with the arduino? If not then it must be done! The arduino simply must venture everywhere! It already went into space! Why not prime numbers?

Go on then :slight_smile: Write this code. It would quickly run out of space in the RAM though.
I can't think of a use for it either so I am not going to venture into that i'm afraid, unless I get really really bored!

Mowcius

Hmm. Always wondered where the ram was on the board...
Alirght I will write a code for it, shouldn't be hard.

I just don't know how to "teach" a code difference between integers and floating points.

I will write it.....eventually....yawn. :-?

I just don't know how to "teach" a code difference between integers and floating points.

Hmm neither do I in that context. I will have to look into it at some point.

Mowcius

The Sieve of Eratosthenes would be a good place to start.

Andrew

I just don't know how to "teach" a code difference between integers and floating points.

You could use a floor / roof function, which would result in an integer... does the C library support these functions?

The Sieve of Eratosthenes would be a good place to start.

Yep, a good place to start. However in the end i would have to approach it differently. I'm aiming for not finding all prime numbers at once, instead one at a time and never stopping until it has run out of ram.

By the way. It has already been done. Just not how I imagined it.
http://www.arduino.cc/playground/Main/PrimeSieve

It uses the method of the sieve of eratosthenes.
Rather than floor/roof (no idea what that is) I could change the code a bit to do each number one by one and as it finds primes it adds those new primes to the bank.

Erm, I guess I should explain myself there... I actually don't have a clue where the need to distinguish floats from ints would arise, but since someone mentioned it above, I though that the two functions would help somehow...

floor drops a value (say 10.21) to the largest preceding integer (so 10)
roof does the opposite (10.21 --> 11)

Prime numbers are always integers.
Floating point numbers are not useful because they lose resolution ((f+1) == f) rather before an int of the same size would do so. A long int can only hold a number up to about 4billion, so it's not all that interesting. An extended precision math library would be ... a fair amount of work.
You only have to check known prime factors up to the square root of the number being tested. (but check (f*f > t) rather than doing a sqrt!)
The Arduino doesn't have enough storage to save a significant list of primes, though I suppose you could do interesting things with an external 2G flash cards :slight_smile: It won't like being written one number at a time, though; you'll have to do some clever caching. (and keep the first several 10s of primes in RAM for quick elimination of "most" numbers.)

So the time for this to have been a homework assignment has passed, right?

The proposed algorithm is very much like the one I used back at college, quite a long time ago. That program was in PDP10 assembler, and ran until the 512k address space of 36bit data was filled up... In general, you don't get to tell if the result of a division is floating point or not; you either divide by an integer and get a quotient (and usually a remainder), or you use floating point for both numbers and hope you get nice even numbers when you divide numbers. Most prime calculators will use integers.

Here's my modern effort. It adds to the original algorithm presented (and to the one I did in college), in that it notices that you can test many numbers for primeness even after the array you can save primes in has become full. You can test primes up to the square of your largest prime...
This code find all the 16 bit primes in about 7 seconds. printing them out increase that to about 16 seconds (there's a lesson there...)

/*
 * Calculate primes, minimizing memory use for microcontrollers.
 * By William Westfield (WestfW), Jan 2010.
 */

#define ARDUINO 1  // lets run on an arduino; a tiny microcontroller board.

/*
 * We test primes by seeing whether they're divisible by previously
 * found primes.  We have limited memory to remember those primes, though.
 * MAXPRIMES is the number we have room for (a guess...)
 */
#define MAXPRIMES 256
unsigned short primes[MAXPRIMES];
unsigned short lastprime;


typedef unsigned char boolean;
#define TRUE 1
#define FALSE 0

#define MAXUSHORT 0xFFFF

boolean done;

#if ARDUINO
#define printprime(d) Serial.println(d);
#define printstring(s) Serial.println(s);
#else
#include <stdio.h>
#define printprime(d) printf("%d\n", d);
#define printstring(s) printf("%s\n", s);
#endif

/*
 * test if a number is prime by seeing if it is evenly divisible
 * by any of the primes we've already found.
 */
boolean testprime (unsigned short t)
{
  int i;
  unsigned int p;  // prime to test with

  for (i=0; i < MAXPRIMES; i++) {
    p = primes[i];

    if (p == 0) {
      return TRUE;   // indivisible by all primes so far
    }
    if ((long)p*(long)p > (long)t) {
      return TRUE;   // indivisible by primes up to sqrt(t)
    }
    if ((t % p) == 0) {
      return FALSE;  // divisible by this factor!
    }
  }   // If this exits, it means we got the end of MAXPRIMES
  printstring("Primes exceed testability at pp, tp, i== ");
  printprime(t);
  printprime(p);
  printprime(i);
  done = TRUE;
  return FALSE;
}

#if ARDUINO
void setup()
{
  Serial.begin(57600);
}
void loop()
#else
int main()
#endif
{
  unsigned short pp;                   /* our possible primt */

  done = FALSE;
  lastprime = 0;
  printprime(2);                   /* 2 is a special case! */

  for (pp = 3; !done; pp += 2) {
    if (testprime(pp)) {
      if (lastprime < MAXPRIMES) {
        /*
       * We can go on testing primes even after we can't save them
              * as long as the number being tested is less than the square
              * of the last prime we've found.
              */
        primes[lastprime++] = pp;
        if (lastprime >= MAXPRIMES) {
          printstring("saved prime array full at pp=");
          printprime(pp);
        }
      }
      printprime(pp);
    }
    if (pp == MAXUSHORT) {
      break;
    }
  }
#if ARDUINO
  printstring("Finished at time ");
  Serial.print(millis());
  while (1) ;  // stop !
#else
  return (0);
#endif
}

For memory efficiency, the Sieve is the best, since the each number can be represented by a single bit, no need for a "unsigned short primes[MAXPRIMES];"

No divisions, no "sqrt" - really it has a lot going for it!

For memory efficiency, the Sieve is the best

I am Not Convinced. I got all the primes up to 65536 using (less than) 512 bytes of memory (plus code.) I could have gotten more if I made the actual proposed primes into longs... (up to about 2627000)

Using the sieve, wouldn't I have needed 65536 bits? (8k bytes), which is more than exists?
(of course, I only STORED primes up to about 1621, which would have taken the sieve only 203 bytes. Sort of.) The sieve is sort of neat if you simply CAN NOT multiply or divide, but that's a pretty artificial limitation.

There is no sqrt() operation in this code; just multiplies and divides.

Total program size is 2568code+100data+675bss