[Processing] Prime Numbers

[Connors]

This is a nice, compact program based on one I wrote in class my senior year in high school.  It finds all prime numbers between 1 and "cap". The assignment stated that we had to optimize the program as much as we could, and the instructor would tell us if he saw our program and knew there was something we could improve. We were only required to make it test one number; the optimization test was we were given a few very large numbers and we saw how long it took to determine that they were prime.

A few notes:
 - It does not bother checking even numbers.
 - The only way the computer can detect a prime number is by checking all possible factors.
 - Modulus returns the remainder of the division of two numbers, and is used to check whether a number is a factor.
 - sqrt() is used because there cannot be any factors larger than the square root of the number . This greatly optimizes the program for checking very large numbers.
 - Processing does not want to use sqrt() with a double, meaning I cannot currently speed-test this with particularly large prime number.

Code: [Select]

int n;
int i;
int cap = 100;
boolean prime;

void setup() { 
  for (n = 3; n < cap; n += 2){
    prime = true;
    for (i = 3; i < sqrt(float(n+1)); i += 2){
      if (n % i == 0) {
        prime = false;
        break;
      }
    }
      if (prime == true)
        println(n);
  }
  println("Done.");
}

[Gan]

Oooh fancy. The higher the number, the longer it takes to determine it's prime-ness.

[Circuit]

Cool, man.  I recently made a similar program in C.  This method of detecting primes is really slow, and not well-suited for finding primes in sequence.  I left my program running for a couple of days and found all of the primes up to 2^31, and saved them to a file... unfortunately, when it was finally done, the file was so big that I couldn't open it. 

Another method that you can use is the Sieve of Eratosthenes.  It behaves opposite of trial division: it gets faster the higher it goes, because it gradually eliminates non-primes by marking off all multiples of known primes.  This involves recording the status of every number (prime or not prime) beginning at 2, so it requires a lot of RAM.

[Connors]

That does sound interesting, how big does a file have to be that it won't open? :L

[Gan]

I'm pretty sure it depends on the text program. If the text program tries to buffer the whole text file, gonna fill up fast.