Taking a different approach from David's answer...
Conclusion / Takeaway / Too Long, Didn't Read
While there are some problems that are better suited to Salesforce than others, the thing to remember is that Salesforce has multiple limits on the computational resources that you can use.
If you're running into a limit, then it's time to alter your approach to the problem you're trying to solve.
You can do a lot of things through Salesforce. You can't do everything, but with enough knowledge and experience, you can push Salesforce to its limits.
On limits and optimization
Salesforce has limits on how many of its resources you can use. This is because Salesforce divides its customers into different "pods" (e.g. na3.salesforce.com, ap10.salesforce.com. eu14.salesforce.com), and there are generally multiple customers on a single pod. This means that Salesforce needs to ensure that one customer on a particular pod won't monopolize the resources of that pod.
So, Salesforce places limits on how much of their resources you are able to use in a single go.
One of the well-known adages in the Computer Science field is
Premature optimization is the root of all evil
Put another way, unless we're running into Salesforce's governor limits, optimization is evil.
In this case, we are running into a governor limit, so optimization is called for.
In most cases, the governor limit that we run into is the limit of 100 soql queries per (synchronous) transaction. In this case, we're running into the CPU limit. The method you've presented for finding prime numbers (the naive method where we divide by all numbers up to n) has an asymptotic computational complexity of
O(sqrt(n)). If you want to find larger primes, you'll need to improve your algorithm so that it uses fewer of Salesforce's CPU cycles.
If you're running into this limit, then it's time to tackle the problem by changing your algorithm.
Limit of the naive algorithm
With no improvements, your provided algorithm can get us up to about the 870th prime number #870 (6,761) without exceeding the CPU limit1, 2
Making improvements to your provided algorithm requires a bit more about math(s) than your average person.
Probably the first optimization that can be made here is to realize that you don't need to check division for all numbers
x is the number you're testing, and
2 <= n < x. You only need to divide by _the primes that you have found up to
x/2 (inclusive). The integers can be bifurcated into two parts, those that are prime, and those that are composite. If a number is not prime (i.e. composite), it will be evenly divisible by a prime number that we have already uncovered.
The asymptotic complexity of this algorithm is roughly the same, but this variant gets us up to roughly prime #2000 (17,389) before running into the governor limits.
Division is an expensive computation, so the less of it we do, the more primes we can find in a given time.
Generally speaking, algorithms that have a computational complexity of
O(n) are grouped with algorithms of computational complexity
O(k*n) where k >= 1. In other words, it doesn't matter what the constant
k is, it's still an
k constant, though, can be important when working with Salesforce. If you algorithm is
O(2*n), the size of your input (
n) is 500, and the CPU time you consume is 570, doubling the size of your input does put you over the CPU limit.
In these situations, it's time to consider using more complex/sophisticated algorithms like the sieve of Eratosthenes. Not only is the asymptotic computational complexity more favorable (
O(k * n(log n)(log(log(n)))) as opposed to
O(n)), but we improve the
k constant as well by substituting our division operations for simple array access and assignment operations.
Implementing the sieve of Eratosthenes, we can get up to around the 925,000th prime number if we additionally use a
List<Boolean> to store whether a given number is prime or not, and only remember the most recent prime number we've found.
At that point, we start running into the governor limit of the size of the heap, rather than the CPU time consumed.
- The naive algorithm gets us to ~ prime # 870
- The improved naive algorithm gets us to ~ prime #2000 (~2.3x your provided, naive algorithm)
- A better algorithm (sieve of Eratosthenes) gets us to ~ prime #925,000 (~1063x your provided algorithm, ~462x the first improvement)
1: The CPU limit in Salesforce is a soft limit, which means we can go above the specified limit if we don't exceed the limit by too much and the activity on the pod you're executing this code on is low
2: The Salesforce CPU time consumed is not 100% deterministic. It depends on whether the code you're running has been cached, and how much activity there is on your particular pod at the time of running your code.