Prime number generator

I've written a sketch that is supposed to generate prime numbers using the modulo operator, but I'm having trouble with it printing anything to the serial monitor. My goal is for it to be as fast as possible, so I'm trying to make it simple to achieve maximum speed. I set the serial communication at 115200 baud on a nano, which should work, although the only thing that comes to mind is that it has a different driver chip than most arduinos (CH340). Here's my code:

/*
  Prime Number Generator
  
  This program starts from the number 3 and prints all
  the primes occuring after it up until 4,294,967,295.
  
*/

long x = 3;    // this variable will contain the number to be tested
long z = 1;    // this variable will increment to indicate how many primes have been found
long y;        // this variable will be the divisor that checks if the number is prime
long start;    // this variable holds the microseconds at the beginning 
boolean prime; // this variable indicates if the number that was tested is prime

void setup(){
  Serial.begin(115200);  // initalize serial communication
}

void loop(){
  start = micros();
  
  do{
    
    for(int y = 3; (y * y) < x; y += 2){
      
      if(x % y == 0){ 
        prime = false;
        break;
      }
    }
    x += 2;
    
  }while(!prime);
    
  Serial.print(x);                        // prints the next prime number
  Serial.print("\t\t");                   // prints two spaces
  Serial.print(z);                        // prints the number of prime numbers generated
  Serial.print("\t\t");                   // prints a space
  z++;
  Serial.println(micros() - start);       // prints the time in microseconds the calculation took
}

The % operator is NOT fast. So, using it as a "fast" way to find prime numbers is a non-starter.

My initial idea was for the for() loop to check if it is prime or not, and the do...while loop to run over again until it found a prime. This would eliminate the need for an if() statement that would print the values if the number was prime, but I don't know it would save that much time.

I thought about using all the primes that occur up to the square root of the number to be tested, but that would probably require an array, which I thought might be slower, but I guess it would probably be faster for the larger numbers if it didn't have to retest divisors like 3 and 9.

As for the y * y < x statement, I chose this method that uses simple multiplication to test if the variable is less than the square root of the number. I could have used y < sqrt(x) , but my guess is that the calculating the square root takes longer. The expressions are algebraically equivalent, since you would come up with y < sqrt(x) if you took the square root of y * y < x .

Concerning the % operator, do you think it would save enough time to start from the ground up by multiplying numbers together and crossing them off the prime number list? Or does the % even matter compared with the clunky Serial.print() statements?

Thanks for all the help ;D .

You can implement the Sieve of Eratosthenes using just an array of bits.

Here is a discussion and implementation of a fast c-algorithm

Prime Number Generators

Been thinking-
I the goal is to be fast I think cheating is the fastest way. 8)
Find a document like this and make a program that generates a sketch like this.

unsigned long primes[7000] = {2,3,5, ..., 70657};

void setup() {
//Serial stuff
}

void loop() {
//Something useful
}

Using all available program memory you can have approx 7000 primes stored as long.

Using Eratosthenes sieve seems problematic due to lack of RAM. To be useful without having to mod or divide you have to at least store all found primes, as well as some other stuff like a reasonable chunk of numbers still to process. Or is there a way around that?

So not cheating and being able to find primes up to large numbers with the memory limit I think you end up in some divisible check loop. Using smart choices of guessed new prime candidates (like: odd numbers excluding every third and fifth) and a list of the first say 4th to 1000th primes to check against before brute force testing would speed up the process.

Using all available program memory you can have approx 7000 primes stored as long.

you can store way more primes if you store the Prime Gaps - A001223 - OEIS - the difference between 2 adjacent primes, then you can go quite far with

uint8_t primeGaps[] = {1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 10, 14, 4, 2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 6, 4, 6, 8, 4, 8, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 12, 8, 4, 8, 4, 6, 12, };

especially if you know that all diffs are even (except the first ones) so you can shift 1 bit. That covers all deltas between 0 and 510.

Also the minimum diff is 2 so the 0 is free to use as an indication that for the next delta 2 bytes need to be used. But I doubt if that is needed as a gap of ~500 occurs somewhere between 10 and 100 * 10e9 - Prime gap - Wikipedia -

Smart!

in code

//
//    FILE: primeGaps.ino
//  AUTHOR: Rob Tillaart
// VERSION: 0.1.00
// PURPOSE: demo
//    DATE: 2014-dec-31
//     URL:
//
// Released to the public domain
//

uint8_t primeGaps[] = {
  1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4,
  6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2,
  4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 10, 14, 4,
  2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 6, 4, 6, 8, 4, 8, 10, 2, 10, 2, 6,
  4, 6, 8, 4, 2, 4, 12, 8, 4, 8, 4, 6, 12,
};

uint32_t start;
uint32_t stop;

void setup()
{
  Serial.begin(115200);
  Serial.println("Start ");

  uint32_t p = 2;
  Serial.println(p);
  for (int i = 0; i < sizeof(primeGaps); i++)
  {
    p += primeGaps[i];
    Serial.print(i);
    Serial.print("\t");
    Serial.println(p);
  }
}

void loop()
{
}

JAndersM:
Smart!

Drawback is that you cannot ask for the 314 th prime number very fast.

From the primes you can generate any gap fast, from the gaps you can only generate primes from the start.

You could mix the two strategies:

  • one array (32 bit) of e.g. every 50 th prime and the primeGaps array, then every prime can still be generated relatively fast, on average ~25 additions.
  • Or one array with every 50th prime and an array with offsets (16 bit), so only one addition is needed...

The question is whether OP needs the generation of primes or just the output.
Using prime gaps is the same thing as copy/pasting the actual list of primes, which is not generating them. Depending on the task given (if this is a school assignment, for example), I would fail any approach that uses a list that requires previous calculation of primes.

the primeGaps stay indeed very small in the first 10000 primes (...104729)
found the following max gaps

[index, gapsize]
1 1
2 2
4 4
9 6
24 8
30 14
99 18
154 20
189 22
217 34
1183 36
1831 44
2225 52
3385 72

note 10K primes defined in a primeGap array would overflow the 8K RAM of a MEGA. (PROGMEM!)

# http://primes.utm.edu/lists/small/10000.txt
P = [
2,3,5,7,11,13,17,19,23,29,

]
m = 0

for x in range(1,10):
 pg = P[x] - P[x-1]
 if pg > m:
 m = pg
 print x, m
    # print pg, ",",
    # if x%25 == 0:
    #    print

If my math is correct you can store prime gaps for the first approx. 30 000 primes (32k minus some code) with robtillaarts method (primes to 350 000) that means: direct look up to 350 000, reasonable fast checking of numbers up to 350 00*350 000 = 1,2 billion. That leaves a sloooow testing of the largest longs that does not divide by any of the stored primes.

If the goal is to look up if a number is a prime or find the n-th prime rather than list them its gets more complicated...

If there is an assignment that does not allow "cheating" with prepared lists. I find it hard to avoid division checking for numbers larger than approx. 600 000 with a 1k RAM limit to store prime differences and other stuff for Eratosthenes. But maybe there are more ingenuous memory saving techniques...

Shpaget:
The question is whether OP needs the generation of primes or just the output.
Using prime gaps is the same thing as copy/pasting the actual list of primes, which is not generating them. Depending on the task given (if this is a school assignment, for example), I would fail any approach that uses a list that requires previous calculation of primes.

Very true, agree 100%

the only advantage of using prime gaps is that you can stuff "more primes" in memory. It is similar to delta coding a series of analogReads(). Normally you need 2 bytes for every measurement but by coding the delta between two consecutive measurements (under the condition they do not change fast) one can store twice as much measurements in memory. Keeping these 'tricks' in mind pushes the limits of embedded.

@JAndersM
Storing primes can be done more efficient in a packet bit array.

discussed - Error in prime printer :( - #4 by robtillaart - Programming Questions - Arduino Forum -

Nice!