2

Problem : What is the 10 001st prime number?

I created program and running fine for 10th, 100th but not able to run for 1000th position giving "System.LimitException: Apex CPU time limit exceeded".

public class ProjectEuler7 
{
    integer count=1;
    boolean isPrime=false;
    List<integer> primeNumberList = new List<integer>();
    public void findPrime(integer position) 
    {
        primeNumberList.add(2);
        for (integer isPrimeNumber=3;isPrimeNumber<10000;isPrimeNumber++) 
        {             
            for (integer j=2;j<isPrimeNumber;j++) 
            {
                if (math.mod(isPrimeNumber, j)== 0)  
                {
                    isPrime=false;
                    break;

                } else {isPrime=true;}
            }
            if (isPrime) 
            {
                count++;
                primeNumberList.add(isPrimeNumber);
                if (count==position) 
                {
                    system.debug('Nth Prime Number =>'+primeNumberList[count-1]);
                    break;
                }

            }

        }
    }
}

Updated Code : ( Using Sieve of Eratosthenes algorithm suggested by Derek ) This is improved version of above code :

public class projectEuler7
{
    List<integer> savePrimeList = new List<integer> ();
    public void findprime(integer n)
    {
        List<boolean> prime = new List<boolean>(n+1);
        for(integer i=0;i<n;i++) 
        {
            prime[i] = true;

        }
        for(integer j = 2; j*j <=n; j++)
        {
            // If prime[j] is not changed, then it is a prime
            if(prime[j] == true)
            {
                // Update all multiples of j
                for(integer i = j*2; i <= n; i += j)
                    prime[i] = false;
            }
        }

        for(integer i = 2; i <= n; i++)
        {
            if(prime[i] == true ) 
            {
                savePrimeList.add(i);
            } 
        }
        integer listSize = savePrimeList.size();
        system.debug(n+'th Prime number is =>'+ savePrimeList[listSize-1] );
    }

}
4

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.

Improvement no.1

Probably the first optimization that can be made here is to realize that you don't need to check division for all numbers n where 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.

Improvement no.2

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 O(n) algorithm.

That 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.

Algorithm growth

To summarize...

  • 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.

| improve this answer | |
  • +1 for a rare use of footnotes in an answer – cropredy Sep 2 '18 at 22:00
  • This is Simply AWESOME !! Thanks Derek for awesome explanation. It took sometime for me to understand your suggestion. Sieve of Eratosthenes algorithm simply awesome and lightning fast. I changed the existing approach and implemented Sieve of Eratosthenes algorithm. When i passed 10001 to my updated version it did not hit any CPU limit and executed very fast. – Sfdc_1184 Sep 3 '18 at 5:01
4

Salesforce isn't, strictly speaking, a general-purpose programming environment. You are simply not going to be able to implement arbitrary-depth prime searches on Salesforce, at least not unless you build in quite a bit of cleverness to monitor governor limits and recurse in something like a Queueable chain. This is a fine example problem in C or Java or Python, but not an especially good one in Apex.

No matter how efficient you make your code, you will find a point if you increase the depth sufficiently at which the processing time is greater than 10 seconds and you hit the 10,000 millisecond CPU time limit in your transaction.

| improve this answer | |
  • Thanks @David Reed for quick response. You are right, I tried few different Approach but no luck. They worked without any issue in Java and Python. This means Apex not for handling complex math problems. :) – Sfdc_1184 Sep 2 '18 at 2:05
  • Apex handles math just fine. You simply have a finite, fixed ceiling on how much processor time you can use in a transaction. This would be a problem you might call out to Heroku, for example, to solve. – David Reed Sep 2 '18 at 2:06
  • Got It. All about CPU time!! – Sfdc_1184 Sep 2 '18 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.