CODEWITHSUNDEEP
performancealgorithmcomparison
Mart Last
Mart Last

Reputation: 13

Which is the quickest of prime generating algorithms?

I was working on an algorithm in Java to find all primes up to a certain number. It was supposed to be an improvement of an earlier method of doing so, which was the following:

public static int[] generatePrimesUpTo(int max)
{
    int[] primes = new int[max];
    primes[0]=2;
    int p = 1;
    for (int i=3;i<max;i+=2)
    {
        if (isPrime(i))
        {
            primes[p]=i;
            p+=1;
        }
    }
    return primes;  
}

public static boolean isPrime(int a)
{
    for (int i=3;i<((int)Math.sqrt(a)+1);i+=2)
    {
        if (a%i==0)
            return false;
    }
    return true;
}

Which just checks for a number N wether or not it is divisible by a smaller number, starting at 2 and ending at sqrt(N).

Now the new approach was to divide N only by smaller prime numbers which the algorithm had found earlier. I thought it would speed up the process quite a lot since it would have to do a lot less calculations.

public static int[] generatePrimes(int num)
{
    int[] primes = new int[num];
    int p = 3;
    primes[0] = 2;
    primes[1] = 3;
    primes[2] = 5;
    boolean prime;
    for (int i=7;i<num;i+=2)
    {
        prime = true;
        for (int j=0;primes[j+1]<(Math.sqrt(i)+1);j++)
        {
            if (i%primes[j]==0)
            {
                prime = false;
                break;
            }
        }
        if (prime)
        {
            primes[p]=i;
            p++;
        }
    }
    return primes;
}

However, there seems to be almost no difference in speed for Nmax = 10^7. For Nmax = 10^8 the new one was 20% faster, but my computer was more active during the calculation of the old one and I tried 10^8 only once.

Could anyone tell me about why this new approach isn't that much faster? Or what I could do to improve the algorithm more?

Thanks in advance!

Upvotes: 1

Views: 55

Answers (2)

Douglas Zare
Douglas Zare

Reputation: 3316

Your second algorithm is faster. I don't know why you only saw a 20% improvement. Here are the results of my tests, with separate implementations:

10^6:
First:  00:00:01.0553813   67240405 steps
Second: 00:00:00.2416291   13927398 steps
Sieve:  00:00:00.0269685    3122044 steps

10^7:
First:  00:00:26.4524301 1741210134 steps
Second: 00:00:04.6647486  286144934 steps
Sieve:  00:00:00.3011046   32850047 steps

10^8:
First:  00:12:00.8986644 46474124250 steps
Second: 00:01:43.1543445  6320928466 steps
Sieve:  00:00:03.6146328   342570200 steps

The last algorithm was the Sieve of Eratosthenes which is a much better algorithm. I implemented all of these in C# for one processor, with the first two based on your code with minor changes like testing primes[j]*primes[j] <= i.

The implementation of the Sieve of Eratosthenes I used was pretty basic, 

Boolean[] definitelyComposite = new Boolean[max]; // initialized automatically to false
int p = 0;
for (long i = 2; i < max; i++)
{
    numSteps++;
    if (!definitelyComposite[i])
    {
        primes[p] = i;
        p++;
        for (long j = i * i; j < max; j += i)
        {
            numSteps++;
            definitelyComposite[j] = true;
        }
    }
}

and it could be improved. For example, except for when i is 2, I could have used j+= 2*i in the loop.

Upvotes: 0

gnasher729
gnasher729

Reputation: 52538

You should think about whether there isn't a method to find all primes in a range that is much faster than checking each prime individually. For example, you will check many numbers whether they are divisible by 73. But the fact is, that you can much faster determine all the numbers divisible by 73 (they are 73, 2*73, 3*73, 4*73 etc.).

By the way: You calculate Math.sqrt (j) in each single iteration of the loop. Moving that calculation outside the loop might make your code considerably faster.

Upvotes: 1

Related Questions