[Ported from SO]
Alright, before we go into that, let's get a little bit of theory sorted. The way you measure the time a particular piece of code takes to run is, mathematically, denoted by the
O(n) notation (big-o notation) where
n is the size of the input.
Your test prime function is of something called
linear complexity meaning that it'll become linearly slow as the size of
n (in this case, your number input) gets large.
For the number
15, the execution context is as follows:
15 % 2 == 0 (FALSE)
15 % 3 == 0 (TRUE)
15 % 14 == 0 (FALSE)
This means that for the number
100, there will be 98 (2 - 99) steps. And this will grow with time. Let's take your number into consideration:
600851475143. The program will execute
for-loop will get triggered
Now, let's consider a clock cycle. Say each instruction takes
1 clock cycle, and a dumbed down version of your loop takes 2, the number
600851475143 will execute
1,201,702,950,286 times. Consider each clock cycle takes
0.0000000625 seconds (for a 16-MHz platform such as the Arduino), the time taken by that code alone is:
0.0000000625 * 1201702950286 = ~75,106 seconds
You see where I am going with this.
Your best best to get this program to work faster is to use a probabilistic test and confirm your findings using this number (or a BigInteger variant thereof).
Your approach is more linear, in the sense that the number of iterations for the
for-loop to check for primality increases with an increasing number. You can plot the CPU cycle time along with the number and you'll realize that this is a rather inefficient way to do this.
I have discrete mathematics at my Uni, so just a word of warning - primality tests and their variants get really messy as you get into the utopia of faster and faster tests. It's a path filled with thorns of mathematics and you should have a seat belt while riding through the jungle! ;)
If you need more information on this, I would be glad to assist! I hope this helped! :)