Thread: Circular prime checking algorithm optimization.

I need help with my algorithm for finding circular primes. If you don't know what a circular prime is, it's when a number, say 179, and its rotations, 179, 917, and 791, are all prime. The algorithm simply checks if the number is a circular prime. The problem I'm using it for is finding the sum of all circular primes under 1,000,000. It's fast enough up until around 100,000, around 6 seconds. What can be done to speed it up?

/**
	 * @param num
	 * @return true if the number is a circular prime
	 * @return false if the number is not a circular prime
	 */
	public static boolean isCircularPrime(long num)
	{
		String number = Long.toString(num);//string containing the number
		if(!isPrime(num))//false if the number isn't prime
		{
			return false;
		}
		else//checks other possibilities 
		{
			if(num>=10)//numbers with two or more digits can only be a circular prime if they are made of 1, 3, 7, or 9
			{
				if(number.contains("2")||number.contains("4")||number.contains("6")||number.contains("8")||number.contains("5")||number.contains("0"))//false if it contains a positive number, five, or zero
				{
					return false;
				}
				else//checks more if it doesn't contain an "illegal" number
				{
					for(int i = 0; i < number.length(); i++)//loops it for the length of the number
					{
						num = rotate(num);//rotates the number once
						if(!isPrime(num))//false if the rotation isn't prime
							return false;
					}
					return true;//true if it the number and all rotations are prime
				}
			}
			else
			{
				return true;
			}
 
		}
 
	}
	//rotates the number once
	public static int rotate(long number)
	{
		long start = number;
		int numdigits = (int) Math.log10((double)number); // would return numdigits - 1
		int multiplier = (int) Math.pow(10.0, (double)numdigits);
		int num = 0;
		long q = number / 10;
		long r = number % 10;
		//1234 = 123;
		number = number / 10;
		number = number + multiplier * r;
		num = (int) number;
		return num;
	}

Sieve of Eratosthenes to get a list of the primes.

//shows all prime numbers to a specified max
	public static int[] primesUpTo(int s) 
	{
		// initially assume all integers are prime
		boolean[] isPrime = new boolean[s + 1];
		for (int i = 2; i <= s; i++) 
		{
			isPrime[i] = true;
		}
		// mark non-primes <= N using Sieve of Eratosthenes
		for (int i = 2; i*i <= s; i++)
		{
			// if i is prime, then mark multiples of i as nonprime
			// suffices to consider mutiples i, i+1, ..., N/i
			if (isPrime[i]) 
			{
				for (int j = i; i*j <= s; j++) 
				{
					isPrime[i*j] = false;
				}
			}
		}
		int primes = 0;
		for (int i = 2; i <= s; i++) {
			if (isPrime[i])
			{
				primes++;
			}
		}
		int[] nums = new int[primes];
		int index = 0;
		for(int i = 2; i <= s; i++)
		{
			if (isPrime[i])
			{
				nums[index] = i;
				index++;
			}
 
		}
 
		return nums;
	}

I get the prime list fast enough, 32 ms. for 1,000,000.

Originally Posted by aesguitar

... It's fast enough up until around 100,000, around 6 seconds. What can be done to speed it up?

I get the prime list fast enough, 32 ms. for 1,000,000.

Hmmm...I got the sieve in similar time, so our systems aren't too different. However...By adding the missing main() and isPrime() functions to your code, I got all of the circular primes (up to and including 999331) in a few hundred milliseconds.

Now, I'm not sure why you are using longs everywhere. Since you are never going above one million, why not just use ints? That might or might not make much difference. I'm guessing there won't be major improvements, but sometimes it's more than you might guess.

Secondly, you don't show your isPrime() function. I'm wondering why you bother to generate the array of primes. Why not just generate the sieve and let isPrime() index into the sieve array? (Isn't that the whole point of having a Sieve?)

Something like:

public class Whatever
{
    static boolean [] sieve; // Instance variable used by isPrime
 
    static void generateSieve(int n) 
    {
        sieve = new boolean[n+1];
        //
        // Your code here to populate the sieve array
        //
    }
 
    static boolean isPrime(int n)
    {
        return sieve[n];
    }
 
    public static void main(String [] args)
    {
        int limit = 1000000;
        generateSieve(limit);
 
        // Take care of the first few "by inspection"
        // Loop through odd numbers after that.
        System.out.println(2);
        System.out.println(3);
        System.out.println(5);
        System.out.println(7);
        int count = 4;
 
        for (int i = 9; i <= limit; i += 2)
        {
            if (isCircularPrime(i))
            {
                System.out.println(i);
                ++count;
            }
        }
        System.out.printf("There are %d circular primes below %d\n", count, limit);
    }
 
 
    // Your other stuff
 
}

I mean, it's gotta save some time by not bothering to check even numbers greater than 2, right? Don't even bother to call isCircularPrime(), right?

Also...

Now, since isPrime() is so fast, thanks to the Sieve, I'm not sure that all of the tests you do inside isCircularPrime() save time. I mean they show a good analysis of what digits can't be in a circular prime, but all of those string.contains() tests (or even one of them) have got to be slower than simply indexing into an array to see whether a given number is prime (I think). If you want to experiment, maybe you can try something like

static boolean isCircularPrime(int num)
BEGIN
 
    Declare an int variable, temp.  Set it equal to num
 
    Make a do{}while() style loop
    LOOP
        IF temp is not prime
        THEN
            Return False
        END IF
        Do an end-around-rotate of decimal digits of temp
    WHILE (temp is not equal to num)
    //
    // The only way it leaves the bottom of the loop
    // is if all the rotations gave a prime
    // Therefore:
    Return True
 
END isCircularPrime function

I think the rotate function could be made without the floating point stuff, but I'm not sure the timing would be much improved by doing the rotation with a string, for example.

Anyhow, with the appropriate isPrime() function and with isCircularPrime() implemented along the lines of the pseudo-code that I showed, I got something like 40-50 milliseconds for generating the Sieve and something around 130-150 milliseconds for the rest of the program. That's not a World Record, but it's a start.


Cheers!

Z

1. If you aren't using a sieve, why did you have a sieve generator in the partial code that you posted?
   
   
2. You said that your code was (apparently) working and you asked for suggestions to speed it up for that particular problem. How big is an array of one million and one booleans? That's the sieve size for your problem, right? I mean, a million booleans isn't much of a strain on any kind of workstation people are using these days, right?
   
   
3. If you want to get meaningful help in the fewest number of iterations, why would you not show us (in your original post) the part that is most likely to be the bottleneck?
   
   
4. The function in your most recent post has an int parameter. The code that you posted previously used longs. I think that getting help in the fewest number of iterations usually would require that you give us exactly what you are working on. I mean, I always test things before I offer suggestions. How the heck can I know what gives improved performance since I don't know what you are using?

Oh, well...


If you want a faster prime number tester that will work for all positive 32-bit integer values and doesn't involve a Sieve: Here's something that can be used with your circular prime program (after changing main() function variables to ints), and finds all of the circular primes less than a million in something like 1500 milliseconds on my machine (compared to something over 15 minutes with your brute-force isPrime and compared to roughly 150 milliseconds with a Sieve).

    static boolean isPrime(int n)
    {
 
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        if (n < 9) return true;
        if (n % 3 == 0) return false;
        if (n % 5 == 0) return false;
 
        // mods[] = {2, 3}   gives no false positives for numbers < 1,373,653
        // {31, 73} gives no false positives for numbers < 9,080,191
        //int mods[] = {2, 3};
        //int mods[] = {31, 73};
 
        // {2,7,61} gives no false positives for numbers < 4,759,123,141
        // However it will give negative for 2, 7, and 61.  2 and
        // 7 have already been taken care of.
        int mods[] = {2, 7, 61};
        if (n == 61)
        {
            return true;
        }
 
        for (int i = 0; i < mods.length; i++)
        {
            if (Witness(mods[i], n)) return false;
        }
        return true;
    }
 
 
    static boolean Witness(int a, long n)
    {
        long t = 0;
        long u = n - 1;
        while ((u & 1) == 0) {
            t++;
            u >>>= 1;
        }
 
        long xi1 = ModularExp(a, u, n);
        long xi2;
 
        for (long i = 0; i < t; i++)
        {
            xi2 = (xi1 * xi1) % n;
            if ((xi2 == 1) && (xi1 != 1) && (xi1 != (n - 1))) return true;
            xi1 = xi2;
        }
        if (xi1 != 1) return true;
        return false;
    }
 
    // Calculates (a**b) modulo n
    static long ModularExp(int a, long b, long n)
    {
        long d = 1;
        int k = 0;
        while ((b >>> k) > 0) k++;
 
        for (int i = k - 1; i >= 0; i--) {
            d = (d * d) % n;
            if (((b >>> i) & 1) > 0) d = (d * a) % n;
        }
        return d;
    }

It starts with "Fermat's little theorem" and goes through a couple of rounds to eliminate false positives (pseudo-primes) for numbers over the entire range of (positive) 32-bit signed integers (and a little more).

Why did I delete almost all of the comments from my prime number code? If people are interested in the theory, they can look up the procedure (I think I gave enough key words for a search engine). If they aren't interested in the theory, and if they only want something that works (or so I claim), well they wouldn't read the comments anyhow.

Cheers,

Z