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.
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.");
}
